Indicación: En el último párrafo de la descripción del problema se ofrece un enunciado breve y formal.

En un futuro lejano, los físicos finalmente han descubierto las leyes naturales del tiempo y la causalidad. Incluso antes del nacimiento de una persona, podemos conocer cierta información sobre su vida mediante un análisis teórico. En otras palabras, la física nos permite «predecir», hasta cierto punto, el «destino» de una persona.

En términos sencillos, el destino de una persona es un árbol enraizado $T$ formado por instantes: la raíz representa el nacimiento y las hojas representan la muerte. Cada nodo que no es una hoja $u$ tiene uno o más hijos $v_1,v_2,\ldots,v_{c_u}$, que representan las distintas posibilidades a las que pueden conducir las $c_u$ decisiones diferentes que esa persona toma en el instante representado por $u$. Formalmente, una decisión es una arista $(u,v_i)$ del árbol, donde $u$ es el padre de $v_i$.

La vida de una persona es un camino sin nodos repetidos desde su nacimiento (la raíz) hasta su muerte (alguna hoja). Cualquier subcamino de ese camino que contenga al menos una arista es una experiencia vital de esa persona. Todas las experiencias vitales que podría tener al vivir su vida de todas las formas posibles se denominan experiencias vitales potenciales. En otras palabras, las experiencias vitales potenciales son todos los caminos de $u$ a $v$ tales que $u,v\in T$, $u\ne v$ y $u$ es un antepasado de $v$. Matemáticamente, una experiencia vital potencial se representa mediante el par ordenado $(u,v)$, y el conjunto de todas las experiencias vitales potenciales del árbol $T$ se denota por $P_T$.

La teoría física no solo nos permite observar el árbol que representa el destino, sino también analizar si algunas experiencias vitales potenciales son «importantes». Cada decisión que toma una persona —es decir, cada arista del árbol— puede ser importante o no importante. Una experiencia vital potencial se denomina importante si y solo si existe una arista importante en el camino correspondiente. Podemos observar que algunas experiencias vitales potenciales son importantes; en otras palabras, podemos obtener mediante observación un conjunto $Q\subseteq P_T$ en el que todas las experiencias vitales potenciales $(u,v)\in Q$ son importantes.

La forma del árbol $T$ ya se ha determinado mediante cálculos, y el conjunto $Q$ ya se ha obtenido mediante observaciones, por lo que la incertidumbre sobre el destino de una persona se ha reducido considerablemente. Sin embargo, esa incertidumbre sigue siendo enorme. Calculémosla: dados el árbol $T$ y el conjunto $Q$, ¿cuántas formas diferentes hay de decidir si cada arista es importante, de modo que se satisfagan las restricciones correspondientes al conjunto observado $Q$? Es decir, para todo $(u,v)\in Q$, debe haber al menos una arista del camino de $u$ a $v$ que se haya declarado importante.

Formalmente: Se dan un árbol $T=(V,E)$ y un conjunto de pares de nodos $Q\subseteq V\times V$, tales que, para todo $(u,v)\in Q$, se cumple $u\ne v$ y $u$ es un antepasado de $v$ en $T$. Aquí, $V$ y $E$ representan, respectivamente, el conjunto de nodos y el conjunto de aristas de $T$. Calcula cuántas funciones diferentes $f:E\to\{0,1\}$ (que asignan a cada arista $e\in E$ un valor $f(e)$ igual a $0$ o $1$) cumplen que, para todo $(u,v)\in Q$, existe una arista $e$ del camino de $u$ a $v$ tal que $f(e)=1$. Como la respuesta puede ser muy grande, solo debes imprimir el resultado módulo $998\,244\,353$ (un número primo).

Entrada

Los datos se leen del archivo destiny.in.

• La primera línea contiene un entero positivo $n$, el tamaño del árbol $T$. Los nodos están numerados de $1$ a $n$, y el nodo $1$ es la raíz.
• Cada una de las siguientes $n-1$ líneas contiene dos números $x_i,y_i$ separados por un espacio, con $1\le x_i,y_i\le n$, que indican que existe una arista entre los nodos $x_i$ e $y_i$. No se garantiza la orientación de esta arista.
• La siguiente línea contiene un entero no negativo $m$, el número de informaciones obtenidas mediante observación.
• Cada una de las siguientes $m$ líneas contiene dos números $u_i,v_i$ separados por un espacio, que indican que $(u_i,v_i)\in Q$. Atención: La entrada puede contener información repetida; es decir, puede haber $i\ne j$ tales que $u_i=u_j$ y $v_i=v_j$.

Consulta la tabla al final del enunciado para conocer el tamaño y las restricciones de los datos de entrada.

Salida

Escribe la salida en el archivo destiny.out.

• Imprime una única línea con un entero: el número de formas módulo $998\,244\,353$.

Ejemplos

Entrada 1

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

Salida 1

10

Nota

Hay 16 formas en total. Las siguientes 6 no satisfacen los requisitos:

• $(1,2),(2,3),(3,5)$ se declaran no importantes y $(3,4)$ se declara importante: no se satisface ninguna restricción de $Q$.
• $(1,2),(2,3),(3,4),(3,5)$ se declaran no importantes: no se satisface ninguna restricción de $Q$.
• $(1,2),(2,3)$ se declaran no importantes y $(3,4),(3,5)$ se declaran importantes: no se satisface $(1,3)$ de $Q$.
• $(1,2),(2,3),(3,4)$ se declaran no importantes y $(3,5)$ se declara importante: no se satisface $(1,3)$ de $Q$.
• $(2,3),(3,5)$ se declaran no importantes y $(1,2),(3,4)$ se declaran importantes: no se satisface $(2,5)$ de $Q$.
• $(2,3),(3,4),(3,5)$ se declaran no importantes y $(1,2)$ se declara importante: no se satisface $(2,5)$ de $Q$.
• En todas las demás formas se satisfacen las restricciones de $Q$.

Entrada 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

Salida 2

960

Ejemplo 3

Consulta destiny/destiny3.in y destiny/destiny3.ans en el directorio del concursante.

Ejemplo 4

Consulta destiny/destiny4.in y destiny/destiny4.ans en el directorio del concursante.

Restricciones

Todos los datos cumplen: $n\le 5\times 10^5$, $m\le 5\times 10^5$. La entrada forma un árbol y, para $1\le i\le m$, $u_i$ siempre es un antepasado de $v_i$.

Árbol binario completo: En este problema, un árbol en el que cada nodo que no es una hoja tiene un hijo izquierdo y un hijo derecho, y todas las hojas tienen la misma profundidad, se denomina árbol binario perfecto. Si numeramos los nodos de un árbol binario perfecto de arriba abajo y de izquierda a derecha, el árbol formado por algunos de los nodos con los números más pequeños se denomina árbol binario completo.