配点 : $800$ 点

問題文

$1$ から $N$ の番号がついた $N$ 頂点の木が与えられます。

$i$ 番目の辺は頂点 $a_i$ と $b_i$ をつないでいます。

すぬけ君は頂点には 0 か 1 のラベルを、辺には AND か OR のラベルをつけることにしました。 頂点と辺へのラベルのつけ方は $2^{2N-1}$ 通りあります。それらのうち下記の条件を満たすものの個数を $998244353$ で割ったあまりを求めてください。

条件：操作 を $N-1$ 回行ったのち、残った頂点についているラベルが 1 になるような操作手順が存在する。操作は下記の手順からなる。

• 辺を $1$ 本選んで縮約する(消された $2$ 個の頂点に書かれていたラベルを $x,y$、消された辺に書かれていたラベルを $\mathrm{op}$ とする)。
• $\mathrm{op}$ が AND ならば $\mathrm{AND}(x,y)$ を、OR ならば $\mathrm{OR}(x,y)$ を新たな頂点にラベルとしてつける。

注記

• 演算 $\mathrm{AND}$ の定義は次の通りです：$\mathrm{AND}(0,0)=(0,1)=(1,0)=0,\mathrm{AND}(1,1)=1$
• 演算 $\mathrm{OR}$ の定義は次の通りです：$\mathrm{OR}(1,1)=(0,1)=(1,0)=1,\mathrm{OR}(0,0)=0$
• 頂点 $s$ と頂点 $t$ を結ぶ辺を縮約する際は、その辺を取り除くと同時に $2$ 頂点を併合します。縮約後の木において、併合により生まれた頂点と頂点 $u$ を結ぶ辺が存在するのは、縮約前の木において $s$ と $u$ を結ぶ辺または $t$ と $u$ を結ぶ辺が存在するときであり、またそのときに限られます。

制約

• 与えられる入力は全て整数
• $2 \leq N \leq 10^{5}$
• $1 \leq a_i, b_i \leq N$
• 与えられるグラフは木

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_1$ $b_1$

$\vdots$

$a_{N-1}$ $b_{N-1}$

出力

問題文中の条件を満たすラベルのつけ方の個数を $998244353$ で割ったあまりを出力せよ。

2
1 2

4

20
7 3
20 18
16 12
7 2
10 5
18 16
16 3
4 11
7 15
8 1
6 1
12 13
15 5
19 17
7 1
9 8
7 17
16 14
11 7

283374562

• $998244353$ で割ったあまりを出力するのを忘れずに。