Wskazówka: w ostatnim akapicie opisu zadania podano krótką, formalną wersję treści.

W odległej przyszłości fizycy wreszcie odkryli prawa natury rządzące czasem i przyczynowością. Jeszcze przed narodzinami człowieka analiza teoretyczna pozwala nam poznać pewne informacje o jego życiu. Innymi słowy, fizyka pozwala nam w pewnym stopniu „przewidywać” jego „los”.

Mówiąc prosto, los człowieka jest ukorzenionym drzewem $T$ złożonym z chwil: korzeń oznacza narodziny, a liście oznaczają śmierć. Każdy wierzchołek $u$, który nie jest liściem, ma co najmniej jedno dziecko $v_1,v_2,\ldots,v_{c_u}$. Oznaczają one różne możliwości wynikające z $c_u$ różnych decyzji podjętych w chwili reprezentowanej przez $u$. Formalnie decyzja to krawędź drzewa $(u,v_i)$, gdzie $u$ jest rodzicem $v_i$.

Życie człowieka jest ścieżką bez powtarzających się wierzchołków, prowadzącą od narodzin (korzenia) do śmierci (pewnego liścia). Każda podścieżka tej ścieżki zawierająca co najmniej jedną krawędź jest doświadczeniem życiowym tego człowieka. Wszystkie doświadczenia, jakie mógłby zdobyć, przeżywając życie na wszystkie możliwe sposoby, nazywamy potencjalnymi doświadczeniami życiowymi. Innymi słowy, są to wszystkie ścieżki od $u$ do $v$, gdzie $u,v\in T$, $u\ne v$, a $u$ jest przodkiem $v$. Matematycznie takie potencjalne doświadczenie oznaczamy uporządkowaną parą $(u,v)$, a zbiór wszystkich potencjalnych doświadczeń drzewa $T$ oznaczamy $P_T$.

Teoria fizyczna pozwala nie tylko obserwować drzewo losu, lecz także analizować, czy pewne potencjalne doświadczenia są „ważne”. Każda decyzja człowieka — każda krawędź drzewa — może być ważna lub nieważna. Potencjalne doświadczenie jest ważne wtedy i tylko wtedy, gdy na odpowiadającej mu ścieżce znajduje się co najmniej jedna ważna krawędź. Możemy zaobserwować, że pewne potencjalne doświadczenia są ważne: otrzymujemy zbiór $Q\subseteq P_T$, w którym każde potencjalne doświadczenie $(u,v)\in Q$ jest ważne.

Kształt drzewa $T$ został już obliczony, a zbiór $Q$ zaobserwowany, więc niepewność dotycząca losu człowieka znacznie zmalała. Nadal jednak jest ogromna. Obliczmy ją: dla danego drzewa $T$ i zbioru $Q$ ile jest różnych sposobów określenia, czy każda krawędź jest ważna, zgodnych z ograniczeniami wynikającymi z obserwacji $Q$? To znaczy: dla każdej pary $(u,v)\in Q$ co najmniej jedna krawędź ścieżki od $u$ do $v$ musi być uznana za ważną.

Formalnie: dane jest drzewo $T=(V,E)$ oraz zbiór par wierzchołków $Q\subseteq V\times V$, taki że dla każdej pary $(u,v)\in Q$ zachodzi $u\ne v$ i $u$ jest przodkiem $v$ w drzewie $T$. Zbiory $V$ i $E$ oznaczają odpowiednio zbiór wierzchołków i zbiór krawędzi drzewa $T$. Oblicz liczbę różnych funkcji $f:E\to\{0,1\}$ (przypisujących każdej krawędzi $e\in E$ wartość $f(e)$ równą $0$ lub $1$), dla których dla każdej pary $(u,v)\in Q$ na ścieżce od $u$ do $v$ istnieje krawędź $e$ spełniająca $f(e)=1$. Ponieważ wynik może być bardzo duży, wypisz go modulo $998\,244\,353$ (liczba pierwsza).

Wejście

Dane należy odczytać z pliku destiny.in.

• Pierwszy wiersz zawiera dodatnią liczbę całkowitą $n$, oznaczającą rozmiar drzewa $T$. Wierzchołki są ponumerowane od $1$ do $n$, a korzeniem jest wierzchołek $1$.
• Każdy z kolejnych $n-1$ wierszy zawiera dwie oddzielone spacją liczby $x_i,y_i$, spełniające $1\le x_i,y_i\le n$, oznaczające krawędź między wierzchołkami $x_i$ i $y_i$. Kierunek tej krawędzi nie jest jednak zagwarantowany.
• Kolejny wiersz zawiera nieujemną liczbę całkowitą $m$, oznaczającą liczbę uzyskanych obserwacji.
• Każdy z kolejnych $m$ wierszy zawiera dwie oddzielone spacją liczby $u_i,v_i$, oznaczające $(u_i,v_i)\in Q$. Uwaga: dane mogą zawierać powtarzające się informacje; mogą istnieć $i\ne j$ takie, że $u_i=u_j$ oraz $v_i=v_j$.

Rozmiary danych i ograniczenia podano w tabeli na końcu treści zadania.

Wyjście

Wynik należy zapisać do pliku destiny.out.

• Wypisz jeden wiersz zawierający jedną liczbę całkowitą: liczbę sposobów modulo $998\,244\,353$.

Przykład

Wejście 1

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

Wyjście 1

10

Uwagi

Łącznie istnieje $16$ sposobów, z których następujące $6$ nie spełnia warunków zadania:

• Krawędzie $(1,2),(2,3),(3,5)$ są nieważne, a $(3,4)$ ważna: żadne ograniczenie ze zbioru $Q$ nie jest spełnione.
• Krawędzie $(1,2),(2,3),(3,4),(3,5)$ są nieważne: żadne ograniczenie ze zbioru $Q$ nie jest spełnione.
• Krawędzie $(1,2),(2,3)$ są nieważne, a $(3,4),(3,5)$ ważne: ograniczenie $(1,3)$ ze zbioru $Q$ nie jest spełnione.
• Krawędzie $(1,2),(2,3),(3,4)$ są nieważne, a $(3,5)$ ważna: ograniczenie $(1,3)$ ze zbioru $Q$ nie jest spełnione.
• Krawędzie $(2,3),(3,5)$ są nieważne, a $(1,2),(3,4)$ ważne: ograniczenie $(2,5)$ ze zbioru $Q$ nie jest spełnione.
• Krawędzie $(2,3),(3,4),(3,5)$ są nieważne, a $(1,2)$ ważna: ograniczenie $(2,5)$ ze zbioru $Q$ nie jest spełnione.
• Wszystkie pozostałe sposoby spełniają ograniczenia ze zbioru $Q$.

Wejście 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

Wyjście 2

960

Przykład 3

Zobacz pliki destiny/destiny3.in i destiny/destiny3.ans w katalogu zawodnika.

Przykład 4

Zobacz pliki destiny/destiny4.in i destiny/destiny4.ans w katalogu zawodnika.

Ograniczenia

Dla wszystkich danych: $n\le 5\times10^5$, $m\le5\times10^5$. Wejście opisuje drzewo i dla $1\le i\le m$ wierzchołek $u_i$ zawsze jest przodkiem $v_i$.

Kompletne drzewo binarne: w tym zadaniu drzewo, w którym każdy wierzchołek niebędący liściem ma lewe i prawe dziecko, a wszystkie liście mają tę samą głębokość, nazywamy doskonałym drzewem binarnym. Ponumerujmy jego wierzchołki od góry do dołu, a na każdym poziomie od lewej do prawej. Drzewo utworzone przez pewną liczbę wierzchołków o najmniejszych numerach nazywamy kompletnym drzewem binarnym.