题目描述

$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)$ を新たな頂点にラベルとしてつける。

输入格式

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

$N$ $a_1$ $b_1$ $\vdots$ $a_{N-1}$ $b_{N-1}$

输出格式

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

题目大意

给定一棵树，给每个点填 $0$ 或 $1$，给每条边填 $\text{AND}$ 或 $\text{OR}$，在所有 $2^{n+n-1}$ 种填法中，计数有多少种满足存在一种缩边的顺序，使得每次把一条边的两个端点缩成一个点，权为原端点与边的运算值，最终点的权为 $1$。

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

提示

注記

• 演算 $\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$
• 与えられるグラフは木

Sample Explanation 2

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