ヒント： 問題文の最後の段落に、簡潔で形式的な問題の記述を用意しています。

遠い未来、物理学者たちはついに時間と因果の自然法則を発見しました。人が生まれる前でさえ、理論的な分析によってその人の人生についていくらかの情報を知ることができます。言い換えれば、物理学によって、人の「運命」をある程度「予言」できるのです。

簡単に言えば、人の運命は時点からなる根付き木 $T$ です。木の根は誕生を、葉は死を表します。葉でない各頂点 $u$ は 1 個以上の子 $v_1,v_2,\ldots,v_{c_u}$ をもち、これらは、その人が $u$ の表す時点で行う $c_u$ 通りの選択から生じる異なる可能性を表します。形式的には、選択は木の辺 $(u,v_i)$ であり、ここで $u$ は $v_i$ の親です。

人の一生は、誕生（根）から死（いずれかの葉）までの、頂点を重複して通らないパスです。このパスのうち少なくとも 1 本の辺を含む任意の部分パスを、その人の人生経験と呼びます。また、あらゆる可能な方法で一生を過ごすことで得られるすべての人生経験を、潜在的な人生経験と呼びます。言い換えれば、潜在的な人生経験とは、$u,v\in T$、$u\ne v$ かつ $u$ が $v$ の祖先であるような、$u$ から $v$ へのすべてのパスです。数学的には、そのような潜在的な人生経験を順序対 $(u,v)$ で表し、木 $T$ のすべての潜在的な人生経験の集合を $\mathcal{P}_T$ と書きます。

物理理論によって、運命を表す木を観測できるだけでなく、潜在的な人生経験の一部が「重要」かどうかも分析できます。人が行うそれぞれの選択、すなわち木の各辺は、重要または重要でないのいずれかです。潜在的な人生経験が重要であるとは、対応するパスに重要な辺が少なくとも 1 本存在することをいいます。潜在的な人生経験の一部が重要であることを観測できます。つまり、集合 $Q\subseteq\mathcal{P}_T$ を観測でき、その中のすべての潜在的な人生経験 $(u,v)\in Q$ は重要です。

木 $T$ の形はすでに計算で確定しており、集合 $Q$ もすでに観測されています。人の運命の不確実性は大きく減りました。それでも不確実性は依然として巨大です。そこで計算してみましょう。与えられた木 $T$ と集合 $Q$ に対し、各辺が重要かどうかを決定する方法で、観測された $Q$ に対応する条件を満たすものは何通りあるでしょうか。すなわち、任意の $(u,v)\in Q$ について、$u$ から $v$ へのパス上に、重要と決定された辺が少なくとも 1 本存在しなければなりません。

形式的には： 木 $T=(V,E)$ と頂点対の集合 $Q\subseteq V\times V$ が与えられます。すべての $(u,v)\in Q$ について、$u\ne v$ であり、$u$ は木 $T$ における $v$ の祖先です。ここで $V$ と $E$ はそれぞれ木 $T$ の頂点集合と辺集合です。任意の $(u,v)\in Q$ について、$u$ から $v$ へのパス上に $f(e)=1$ となる辺 $e$ が存在するような、異なる関数 $f:E\to\{0,1\}$（各辺 $e\in E$ の $f(e)$ の値を $0$ または $1$ にするもの）の個数を求めてください。答えは非常に大きくなり得るため、$998\,244\,353$（素数）で割った余りだけを出力してください。

入力

ファイル destiny.in からデータを読み込みます。

• 1 行目には正整数 $n$ が含まれ、木 $T$ の大きさを表します。木の頂点には $1$ から $n$ までの番号が付いており、頂点 $1$ が根です。
• 続く $n-1$ 行にはそれぞれ、空白で区切られた 2 つの数 $x_i,y_i$ が含まれます。$1\le x_i,y_i\le n$ を満たし、頂点 $x_i$ と $y_i$ の間に辺が存在することを表しますが、この辺の向きは保証されません。
• 続く 1 行には非負整数 $m$ が含まれ、観測された情報の件数を表します。
• 続く $m$ 行にはそれぞれ、空白で区切られた 2 つの数 $u_i,v_i$ が含まれ、$(u_i,v_i)\in Q$ を表します。注意： 入力には重複した情報が含まれることがあります。つまり、$i\ne j$ であっても $u_i=u_j$ かつ $v_i=v_j$ となることがあります。

入力データの大きさと制約については、問題文末尾の表を参照してください。

出力

ファイル destiny.out に出力します。

• 方法の数を $998\,244\,353$ で割った余りを表す整数を、1 行に 1 つだけ出力してください。

入出力例

入力 1

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

出力 1

10

注記

全部で 16 通りの方法があり、そのうち条件を満たさないものは次の 6 通りです。

• $(1,2),(2,3),(3,5)$ を重要でないとし、$(3,4)$ を重要とする：集合 $Q$ のどの条件も満たされません。
• $(1,2),(2,3),(3,4),(3,5)$ を重要でないとする：集合 $Q$ のどの条件も満たされません。
• $(1,2),(2,3)$ を重要でないとし、$(3,4),(3,5)$ を重要とする：集合 $Q$ の $(1,3)$ が満たされません。
• $(1,2),(2,3),(3,4)$ を重要でないとし、$(3,5)$ を重要とする：集合 $Q$ の $(1,3)$ が満たされません。
• $(2,3),(3,5)$ を重要でないとし、$(1,2),(3,4)$ を重要とする：集合 $Q$ の $(2,5)$ が満たされません。
• $(2,3),(3,4),(3,5)$ を重要でないとし、$(1,2)$ を重要とする：集合 $Q$ の $(2,5)$ が満たされません。
• それ以外の方法では、集合 $Q$ のすべての条件が満たされます。

入力 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

出力 2

960

入出力例 3

選手用ディレクトリ内の destiny/destiny3.in と destiny/destiny3.ans を参照してください。

入出力例 4

選手用ディレクトリ内の destiny/destiny4.in と destiny/destiny4.ans を参照してください。

制約

すべてのデータについて： $n\le 5\times10^5$、$m\le 5\times10^5$ を満たします。入力は木を構成し、$1\le i\le m$ に対して、$u_i$ は常に $v_i$ の祖先です。

完全二分木： この問題では、葉でないすべての頂点が左右の子をもち、すべての葉の深さが等しい木を、満二分木と呼びます。満二分木の頂点に上から下、左から右の順で番号を付けたとき、番号が小さい方からいくつかの頂点で構成される木を、完全二分木と呼びます。