AT_agc052_f [AGC052F] Tree Vertices XOR

[problemUrl]: https://atcoder.jp/contests/agc052/tasks/agc052_f $ N $ 頂点の木が与えられます。 木の頂点には $ 1 $ から $ N $ までの番号が付けられており、$ i $ 番目の辺は頂点 $ u_i,\ v_i $ を結びます。 はじめ、木の各頂点には $ 1 $ という数が書かれています。 $ 1 $ 回の操作で、あなたは以下を行えます。 - 木から頂点 $ v $ を選ぶ。$ v $ に隣接する頂点全てに書き込まれた値の **XOR** が $ X $ であるとする。$ v $ に書かれた値が $ a_v $ であるとして、この値を $ (a_v\ \mathrm{XOR}\ X) $ に置き換える。 この操作を任意の有限回（$ 0 $ 回も含む）行えるとして、得られる木の形態は何通りあるでしょうか。この数は大きい可能性があるため、これを $ 998244353 $ で割った余りを出力してください。 ここで、木の $ 2 $ つの形態は、書かれた数が異なるような頂点 $ v $ が存在するときに異なるとみなされます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $

初期状態から得られる木の形態の個数を $ 998244353 $ で割った余りを出力せよ。

### 制約 - $ 3\ \le\ N\ \le\ 2\cdot\ 10^5 $ - $ 1\le\ u_i,\ v_i\ \le\ N $ - $ u_i\ \neq\ v_i $ - 入力が表すグラフは木である。 ### Sample Explanation 1 頂点 $ 1,2,3,4 $ に $ a,b,c,d $ が書かれている形態を $ abcd $ と表すと、到達可能な形態は $ 1111 $, $ 1110 $, $ 1100 $, $ 1000 $, $ 0111 $, $ 0110 $, $ 0100 $, $ 0011 $, $ 0010 $, $ 0001 $ です。