Indication : le dernier paragraphe de l'énoncé fournit une description brève et formelle du problème.

Dans un avenir lointain, les physiciens ont enfin découvert les lois naturelles du temps et de la causalité. Avant même la naissance d'une personne, une analyse théorique permet de connaître certaines informations sur sa vie. Autrement dit, la physique nous permet, dans une certaine mesure, de « prédire » le « destin » d'une personne.

Pour simplifier, le destin d'une personne est un arbre enraciné $T$ constitué d'instants : sa racine représente la naissance, et ses feuilles représentent la mort. Chaque sommet non feuille $u$ possède un ou plusieurs enfants $v_1, v_2, \ldots, v_{c_u}$, qui représentent les différentes possibilités auxquelles peuvent mener les $c_u$ choix que cette personne peut faire à l'instant représenté par $u$. Formellement, un choix est une arête $(u, v_i)$ de l'arbre, où $u$ est le parent de $v_i$.

La vie d'une personne est un chemin sans sommet répété allant de la naissance (la racine) à la mort (une certaine feuille). Tout sous-chemin de ce chemin contenant au moins une arête est une expérience de vie de cette personne. Toutes les expériences de vie qu'elle pourrait avoir en vivant sa vie de toutes les manières possibles sont appelées expériences de vie potentielles. Autrement dit, les expériences de vie potentielles sont tous les chemins de $u$ à $v$ tels que $u, v \in T$, $u \ne v$, et $u$ est un ancêtre de $v$. Mathématiquement, une telle expérience de vie potentielle est notée par le couple ordonné $(u, v)$, et l'ensemble de toutes les expériences de vie potentielles de l'arbre $T$ est noté $\mathcal{P}_T$.

La théorie physique permet non seulement d'observer l'arbre représentant le destin, mais aussi d'analyser si certaines expériences de vie potentielles sont « importantes ». Chaque choix fait par une personne — c'est-à-dire chaque arête de l'arbre — peut être important ou non important. Une expérience de vie potentielle est dite importante si et seulement si le chemin correspondant contient au moins une arête importante. Nous pouvons observer que certaines expériences de vie potentielles sont importantes : autrement dit, nous pouvons obtenir par observation un ensemble $\mathcal{Q} \subseteq \mathcal{P}_T$ tel que toutes les expériences de vie potentielles $(u, v) \in \mathcal{Q}$ sont importantes.

La structure de l'arbre $T$ a déjà été déterminée par le calcul, et l'ensemble $\mathcal{Q}$ a déjà été observé. L'incertitude sur le destin d'une personne a donc considérablement diminué. Elle reste cependant immense : calculons-la ! Pour un arbre $T$ et un ensemble $\mathcal{Q}$ donnés, combien existe-t-il de façons différentes de décider si chaque arête est importante, tout en respectant les contraintes correspondant à l'ensemble observé $\mathcal{Q}$ ? Pour tout $(u, v) \in \mathcal{Q}$, au moins une arête du chemin de $u$ à $v$ doit donc être déclarée importante.

Formellement : on donne un arbre $T = (V, E)$ et un ensemble de couples de sommets $\mathcal{Q} \subseteq V \times V$, tels que, pour tout $(u, v) \in \mathcal{Q}$, on a $u \ne v$ et $u$ est un ancêtre de $v$ dans l'arbre $T$. Les ensembles $V$ et $E$ désignent respectivement les sommets et les arêtes de $T$. Déterminez le nombre de fonctions distinctes $f : E \to \{0, 1\}$ (qui attribuent à chaque arête $e \in E$ une valeur $f(e)$ égale à $0$ ou $1$) telles que, pour tout $(u, v) \in \mathcal{Q}$, il existe une arête $e$ sur le chemin de $u$ à $v$ vérifiant $f(e) = 1$. La réponse pouvant être très grande, vous devez seulement afficher son reste modulo $998\,244\,353$ (un nombre premier).

Entrée

Les données sont lues dans le fichier destiny.in.

• La première ligne contient un entier strictement positif $n$, la taille de l'arbre $T$. Ses sommets sont numérotés de $1$ à $n$, et le sommet $1$ est la racine.
• Chacune des $n - 1$ lignes suivantes contient deux nombres $x_i, y_i$ séparés par un espace, avec $1 \le x_i, y_i \le n$, indiquant qu'une arête relie les sommets $x_i$ et $y_i$ de l'arbre. L'orientation de cette arête n'est toutefois pas garantie.
• La ligne suivante contient un entier non négatif $m$, le nombre d'informations obtenues par observation.
• Chacune des $m$ lignes suivantes contient deux nombres $u_i, v_i$ séparés par un espace, indiquant que $(u_i, v_i) \in \mathcal{Q}$. Attention : les données peuvent contenir des informations répétées. Autrement dit, il peut exister $i \ne j$ tels que $u_i = u_j$ et $v_i = v_j$.

Les tailles et les contraintes des données d'entrée figurent dans le tableau à la fin de l'énoncé.

Sortie

Écrivez la réponse dans le fichier destiny.out.

• Affichez une seule ligne contenant un entier : le nombre de façons possibles modulo $998\,244\,353$.

Exemples

Entrée 1

5
1 2
2 3
3 4
3 5
2
1 3
2 5

Sortie 1

10

Remarque

Il y a $16$ façons au total, dont les $6$ suivantes ne satisfont pas les conditions :

• $(1, 2), (2, 3), (3, 5)$ sont déclarées non importantes et $(3, 4)$ importante : aucune contrainte de $\mathcal{Q}$ n'est satisfaite.
• $(1, 2), (2, 3), (3, 4), (3, 5)$ sont déclarées non importantes : aucune contrainte de $\mathcal{Q}$ n'est satisfaite.
• $(1, 2), (2, 3)$ sont déclarées non importantes et $(3, 4), (3, 5)$ importantes : la contrainte $(1, 3)$ de $\mathcal{Q}$ n'est pas satisfaite.
• $(1, 2), (2, 3), (3, 4)$ sont déclarées non importantes et $(3, 5)$ importante : la contrainte $(1, 3)$ de $\mathcal{Q}$ n'est pas satisfaite.
• $(2, 3), (3, 5)$ sont déclarées non importantes et $(1, 2), (3, 4)$ importantes : la contrainte $(2, 5)$ de $\mathcal{Q}$ n'est pas satisfaite.
• $(2, 3), (3, 4), (3, 5)$ sont déclarées non importantes et $(1, 2)$ importante : la contrainte $(2, 5)$ de $\mathcal{Q}$ n'est pas satisfaite.
• Toutes les autres façons satisfont les contraintes de $\mathcal{Q}$.

Entrée 2

15
2 1
3 1
4 3
5 2
6 3
7 6
8 4
9 5
10 7
11 5
12 10
13 3
14 9
15 8
6
3 12
5 11
2 5
3 13
8 15
1 13

Sortie 2

960

Exemple 3

Voir destiny/destiny3.in et destiny/destiny3.ans dans le répertoire du candidat.

Exemple 4

Voir destiny/destiny4.in et destiny/destiny4.ans dans le répertoire du candidat.

Contraintes

Pour toutes les données : $n \le 5 \times 10^5$ et $m \le 5 \times 10^5$. L'entrée forme un arbre et, pour $1 \le i \le m$, $u_i$ est toujours un ancêtre de $v_i$.

Arbre binaire complet : dans ce problème, un arbre dans lequel chaque sommet non feuille possède un enfant gauche et un enfant droit, et où toutes les feuilles ont la même profondeur, est appelé arbre binaire parfait. Numérotons les sommets d'un arbre binaire parfait de haut en bas et de gauche à droite. L'arbre formé par un certain nombre de sommets portant les plus petits numéros est appelé arbre binaire complet.