AT_arc142_d [ARC142D] Deterministic Placing

[problemUrl]: https://atcoder.jp/contests/arc142/tasks/arc142_d $ 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 $ は一意に定まる。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ \vdots $ $ a_{N-1} $ $ b_{N-1} $

答えを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ a_i\ \lt\ b_i\ \leq\ N $ - 与えられるグラフは木である - 入力はすべて整数 ### Sample Explanation 1 次の $ 2 $ 通りが条件を満たします。 - 頂点 $ 1 $ と頂点 $ 2 $ を選び、駒を置く。 - 頂点 $ 1 $ と頂点 $ 3 $ を選び、駒を置く。 頂点を $ 1 $ 個以上選ぶ必要があることに気を付けてください。 ### Sample Explanation 2 条件を満たす駒の置き方が存在しない場合があります。