Hinweis: Im letzten Absatz der Aufgabenbeschreibung geben wir eine kurze, formale Beschreibung der Aufgabe.

In ferner Zukunft haben Physiker endlich die Naturgesetze von Zeit und Kausalität entdeckt. Schon bevor ein Mensch geboren wird, können wir durch theoretische Analyse einiges über sein Leben erfahren. Mit anderen Worten ermöglicht uns die Physik, das „Schicksal“ eines Menschen bis zu einem gewissen Grad „vorherzusagen“.

Vereinfacht dargestellt ist das Schicksal eines Menschen ein gewurzelter Baum $T$ aus Zeitpunkten: Seine Wurzel steht für die Geburt, seine Blätter für den Tod. Jeder innere Knoten $u$ besitzt einen oder mehrere Kinder $v_1,v_2,\ldots,v_{c_u}$. Diese stellen die verschiedenen Möglichkeiten dar, zu denen die $c_u$ verschiedenen Entscheidungen führen können, die dieser Mensch zum Zeitpunkt $u$ trifft. Formal ist eine Entscheidung eine Kante $(u,v_i)$ des Baums, wobei $u$ der Elternknoten von $v_i$ ist.

Das Leben eines Menschen ist ein Pfad ohne wiederholte Knoten von der Geburt (der Wurzel) bis zum Tod (einem Blatt). Jeder Teilpfad davon, der mindestens eine Kante enthält, ist ein Lebensabschnitt dieses Menschen. Alle Lebensabschnitte, die er oder sie beim Durchleben aller möglichen Leben haben könnte, heißen potenzielle Lebensabschnitte. Mit anderen Worten sind dies alle Pfade von $u$ nach $v$ mit $u,v\in T$, $u\ne v$ und $u$ als Vorfahren von $v$. Mathematisch wird ein solcher potenzieller Lebensabschnitt als geordnetes Paar $(u,v)$ bezeichnet. Die Menge aller potenziellen Lebensabschnitte des Baums $T$ heißt $P_T$.

Die physikalische Theorie erlaubt uns nicht nur, den Schicksalsbaum zu beobachten, sondern auch festzustellen, ob manche potenziellen Lebensabschnitte „wichtig“ sind. Jede Entscheidung eines Menschen, also jede Kante des Baums, kann wichtig oder unwichtig sein. Ein potenzieller Lebensabschnitt heißt genau dann wichtig, wenn sein Pfad mindestens eine wichtige Kante enthält. Wir können beobachten, dass einige potenzielle Lebensabschnitte wichtig sind: Wir können also eine Menge $Q\subseteq P_T$ ermitteln, deren sämtliche potenziellen Lebensabschnitte $(u,v)\in Q$ wichtig sind.

Die Struktur von $T$ ist längst berechnet und die Menge $Q$ längst beobachtet worden; die Ungewissheit über das Schicksal eines Menschen ist dadurch stark verringert. Dennoch bleibt sie gewaltig. Berechne für den gegebenen Baum $T$ und die Menge $Q$, auf wie viele verschiedene Arten jede Kante als wichtig oder unwichtig festgelegt werden kann, sodass die durch $Q$ beobachteten Bedingungen erfüllt sind: Für jedes $(u,v)\in Q$ muss mindestens eine Kante auf dem Pfad von $u$ nach $v$ als wichtig festgelegt sein.

Formal: Gegeben sind ein Baum $T=(V,E)$ und eine Menge von Knotenpaaren $Q\subseteq V\times V$, sodass für jedes $(u,v)\in Q$ gilt: $u\ne v$, und $u$ ist ein Vorfahr von $v$ in $T$. Dabei sind $V$ und $E$ die Knoten- beziehungsweise Kantenmenge von $T$. Bestimme die Anzahl verschiedener Funktionen $f:E\to\{0,1\}$ (für jede Kante $e\in E$ wird $f(e)$ auf $0$ oder $1$ gesetzt), sodass für jedes $(u,v)\in Q$ auf dem Pfad von $u$ nach $v$ eine Kante $e$ mit $f(e)=1$ existiert. Da die Antwort sehr groß sein kann, gib nur ihren Rest modulo $998\,244\,353$ (eine Primzahl) aus.

Eingabe

Lies die Daten aus der Datei destiny.in.

• Die erste Zeile enthält eine positive ganze Zahl $n$, die Größe des Baums $T$. Seine Knoten sind von $1$ bis $n$ nummeriert; Knoten $1$ ist die Wurzel.
• Die nächsten $n-1$ Zeilen enthalten jeweils zwei durch ein Leerzeichen getrennte Zahlen $x_i,y_i$ mit $1\le x_i,y_i\le n$. Sie geben an, dass eine Kante zwischen den Knoten $x_i$ und $y_i$ existiert; die Richtung dieser Kante ist jedoch nicht festgelegt.
• Die nächste Zeile enthält eine nichtnegative ganze Zahl $m$, die Anzahl der beobachteten Informationen.
• Die nächsten $m$ Zeilen enthalten jeweils zwei durch ein Leerzeichen getrennte Zahlen $u_i,v_i$, die $(u_i,v_i)\in Q$ angeben. Beachte: Die Eingabe kann wiederholte Informationen enthalten. Es können also $i\ne j$ mit $u_i=u_j$ und $v_i=v_j$ existieren.

Die Größen und Beschränkungen der Eingabedaten stehen in der Tabelle am Ende der Aufgabe.

Ausgabe

Schreibe die Ausgabe in die Datei destiny.out.

• Gib in einer einzigen Zeile eine ganze Zahl aus: die Anzahl der Möglichkeiten modulo $998\,244\,353$.

Beispiele

Eingabe 1

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

Ausgabe 1

10

Hinweis

Es gibt insgesamt 16 Möglichkeiten. Die folgenden 6 erfüllen die Bedingungen nicht:

• $(1,2),(2,3),(3,5)$ sind unwichtig und $(3,4)$ ist wichtig: Keine Bedingung aus $Q$ ist erfüllt.
• $(1,2),(2,3),(3,4),(3,5)$ sind unwichtig: Keine Bedingung aus $Q$ ist erfüllt.
• $(1,2),(2,3)$ sind unwichtig und $(3,4),(3,5)$ sind wichtig: Die Bedingung $(1,3)$ aus $Q$ ist nicht erfüllt.
• $(1,2),(2,3),(3,4)$ sind unwichtig und $(3,5)$ ist wichtig: Die Bedingung $(1,3)$ aus $Q$ ist nicht erfüllt.
• $(2,3),(3,5)$ sind unwichtig und $(1,2),(3,4)$ sind wichtig: Die Bedingung $(2,5)$ aus $Q$ ist nicht erfüllt.
• $(2,3),(3,4),(3,5)$ sind unwichtig und $(1,2)$ ist wichtig: Die Bedingung $(2,5)$ aus $Q$ ist nicht erfüllt.
• Bei allen anderen Möglichkeiten sind sämtliche Bedingungen aus $Q$ erfüllt.

Eingabe 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

Ausgabe 2

960

Beispiele 3

Siehe destiny/destiny3.in und destiny/destiny3.ans im Teilnehmerverzeichnis.

Beispiele 4

Siehe destiny/destiny4.in und destiny/destiny4.ans im Teilnehmerverzeichnis.

Beschränkungen

Für alle Daten gilt: $n\le 5\times 10^5$ und $m\le 5\times 10^5$. Die Eingabe bildet einen Baum, und für $1\le i\le m$ ist $u_i$ stets ein Vorfahr von $v_i$.

Vollständiger Binärbaum: In dieser Aufgabe heißt ein Baum, in dem jeder innere Knoten sowohl ein linkes als auch ein rechtes Kind besitzt und alle Blätter dieselbe Tiefe haben, perfekter Binärbaum. Nummeriert man seine Knoten von oben nach unten und von links nach rechts, so heißt der von einigen Knoten mit den kleinsten Nummern gebildete Baum vollständiger Binärbaum.