Dica: No último parágrafo da descrição do problema, fornecemos uma descrição breve e formal.

Num futuro distante, os físicos finalmente descobriram as leis naturais do tempo e da causalidade. Mesmo antes de uma pessoa nascer, podemos conhecer algumas informações sobre a sua vida por meio de uma análise teórica. Por outras palavras, a física permite-nos, até certo ponto, «prever» o «destino» de uma pessoa.

Em termos simples, o destino de uma pessoa é uma árvore enraizada $T$ formada por instantes: a raiz representa o nascimento, enquanto as folhas representam a morte. Cada vértice não folha $u$ tem um ou mais filhos $v_1,v_2,\ldots,v_{c_u}$, que representam as diferentes possibilidades a que podem conduzir as $c_u$ escolhas distintas que essa pessoa faz no instante representado por $u$. Formalmente, uma escolha é uma aresta $(u,v_i)$ da árvore, em que $u$ é o pai de $v_i$.

A vida de uma pessoa é um caminho sem vértices repetidos que vai do nascimento (a raiz) à morte (uma das folhas). Qualquer subcaminho desse caminho que contenha pelo menos uma aresta é uma experiência de vida dessa pessoa. Todas as experiências de vida que ela poderia ter ao viver de todas as formas possíveis são chamadas experiências de vida potenciais. Por outras palavras, as experiências de vida potenciais são todos os caminhos de $u$ a $v$ em que $u,v\in T$, $u\ne v$ e $u$ é antepassado de $v$. Matematicamente, uma experiência de vida potencial é representada pelo par ordenado $(u,v)$, e o conjunto de todas as experiências de vida potenciais da árvore $T$ é denotado por $\mathcal P_T$.

A teoria física não só nos permite observar a árvore que representa o destino, como também analisar se algumas experiências de vida potenciais são «importantes». Cada escolha feita por uma pessoa, isto é, cada aresta da árvore, pode ser importante ou não importante. Uma experiência de vida potencial é chamada importante se, e somente se, existir uma aresta importante no caminho correspondente. Podemos observar que algumas experiências de vida potenciais são importantes: por outras palavras, podemos obter por observação um conjunto $Q\subseteq\mathcal P_T$ no qual todas as experiências de vida potenciais $(u,v)\in Q$ são importantes.

A estrutura da árvore $T$ já foi determinada por cálculo e o conjunto $Q$ já foi observado, pelo que a incerteza sobre o destino de uma pessoa foi bastante reduzida. Mas essa incerteza continua a ser enorme. Vamos calculá-la: dados a árvore $T$ e o conjunto $Q$, quantas maneiras diferentes existem de determinar se cada aresta é importante, de modo a satisfazer as restrições correspondentes ao conjunto observado $Q$? Isto é, para todo $(u,v)\in Q$, deve existir uma aresta no caminho de $u$ a $v$ que seja considerada importante.

Formalmente: São dados uma árvore $T=(V,E)$ e um conjunto de pares de vértices $Q\subseteq V\times V$, tais que, para todo $(u,v)\in Q$, temos $u\ne v$ e $u$ é antepassado de $v$ na árvore $T$. Aqui, $V$ e $E$ representam, respetivamente, o conjunto de vértices e o conjunto de arestas de $T$. Determine quantas funções distintas $f:E\to\{0,1\}$ existem (atribuir a cada aresta $e\in E$ um valor $f(e)$ igual a $0$ ou $1$), tais que, para qualquer $(u,v)\in Q$, exista uma aresta $e$ no caminho de $u$ a $v$ com $f(e)=1$. Como a resposta pode ser muito grande, basta apresentar o resultado módulo $998\,244\,353$ (um número primo).

Entrada

Leia os dados do ficheiro destiny.in.

• A primeira linha contém um inteiro positivo $n$, que representa o tamanho da árvore $T$. Os vértices são numerados de $1$ a $n$, e o vértice $1$ é a raiz.
• Cada uma das $n-1$ linhas seguintes contém dois números $x_i,y_i$ separados por um espaço, com $1\le x_i,y_i\le n$, indicando que existe uma aresta entre os vértices $x_i$ e $y_i$. A orientação dessa aresta não é garantida.
• A linha seguinte contém um inteiro não negativo $m$, que representa a quantidade de informações obtidas por observação.
• Cada uma das $m$ linhas seguintes contém dois números $u_i,v_i$ separados por um espaço, indicando que $(u_i,v_i)\in Q$. Atenção: Os dados de entrada podem conter informações repetidas. Por outras palavras, podem existir $i\ne j$ tais que $u_i=u_j$ e $v_i=v_j$.

Consulte a tabela no final do enunciado para os tamanhos e as restrições dos dados de entrada.

Saída

Escreva no ficheiro destiny.out.

• A saída contém apenas uma linha com um inteiro, que representa o número de maneiras módulo $998\,244\,353$.

Exemplos

Entrada 1

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

Saída 1

10

Nota

Há 16 maneiras no total, das quais as seguintes 6 não satisfazem os requisitos:

• $(1,2),(2,3),(3,5)$ são consideradas não importantes e $(3,4)$ é considerada importante: nenhuma restrição de $Q$ é satisfeita.
• $(1,2),(2,3),(3,4),(3,5)$ são consideradas não importantes: nenhuma restrição de $Q$ é satisfeita.
• $(1,2),(2,3)$ são consideradas não importantes e $(3,4),(3,5)$ são consideradas importantes: a restrição $(1,3)$ de $Q$ não é satisfeita.
• $(1,2),(2,3),(3,4)$ são consideradas não importantes e $(3,5)$ é considerada importante: a restrição $(1,3)$ de $Q$ não é satisfeita.
• $(2,3),(3,5)$ são consideradas não importantes e $(1,2),(3,4)$ são consideradas importantes: a restrição $(2,5)$ de $Q$ não é satisfeita.
• $(2,3),(3,4),(3,5)$ são consideradas não importantes e $(1,2)$ é considerada importante: a restrição $(2,5)$ de $Q$ não é satisfeita.
• Em todas as outras maneiras, todas as restrições de $Q$ são satisfeitas.

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

Saída 2

960

Exemplo 3

Consulte destiny/destiny3.in e destiny/destiny3.ans no diretório do concorrente.

Exemplo 4

Consulte destiny/destiny4.in e destiny/destiny4.ans no diretório do concorrente.

Restrições

Todos os dados satisfazem: $n\le 5\times10^5$, $m\le 5\times10^5$. A entrada forma uma árvore e, para $1\le i\le m$, $u_i$ é sempre antepassado de $v_i$.

Árvore binária completa: Neste problema, uma árvore em que cada vértice não folha tem um filho esquerdo e um filho direito, e todas as folhas têm a mesma profundidade, é chamada árvore binária perfeita. Numerando os vértices de uma árvore binária perfeita de cima para baixo e da esquerda para a direita, a árvore formada por alguns dos vértices com os menores números é chamada árvore binária completa.