配点 : $800$ 点

問題文

$N$ 頂点の木があり、各頂点には $1,\ldots,N$ と番号が付けられています。 $i=1,\ldots,N-1$ に対し、 $i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結びます。 この木の各頂点に高々 $1$ 個の駒が置かれた状態に対する操作を次のように定めます。

• すべての駒を、同時に、隣接する頂点のうちの $1$ つへ移動させる。

また、以下の条件を満たす操作を 良い操作 と呼びます。

• すべての辺について、その辺を通して移動する駒は高々 $1$ 個である。
• 操作後に各頂点に置かれている駒は高々 $1$ 個である。

高橋君は $1$ 個以上の頂点を選び、駒を $1$ 個ずつ置くことにしました。 駒を置く方法は $2^N-1$ 通りありますが、そのうち次の条件を満たすものの個数を $998244353$ で割った余りを求めてください。

• すべての非負整数 $K$ について以下の条件を満たす。 - 良い操作を $K$ 回行うことができる。
  • 良い操作を $K$ 回行った時点で駒が置かれている頂点の集合を $S_K$ とする。この時、 $S_K$ は一意に定まる。
• 良い操作を $K$ 回行うことができる。
• 良い操作を $K$ 回行った時点で駒が置かれている頂点の集合を $S_K$ とする。この時、 $S_K$ は一意に定まる。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq a_i \lt b_i \leq N$
• 与えられるグラフは木である
• 入力はすべて整数

入力

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

$N$

$a_1$ $b_1$

$\vdots$

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

出力

答えを出力せよ。

3
1 2
1 3

2

次の $2$ 通りが条件を満たします。

• 頂点 $1$ と頂点 $2$ を選び、駒を置く。
• 頂点 $1$ と頂点 $3$ を選び、駒を置く。

頂点を $1$ 個以上選ぶ必要があることに気を付けてください。

7
1 2
1 3
2 4
2 5
3 6
3 7

0

条件を満たす駒の置き方が存在しない場合があります。

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

100