All Even

問題文

$N$ 頂点の木 $T$ が与えられます。各頂点には $1$ から $N$ の番号が付いており、 $i$ 番目の辺は頂点 $u_i$ と $v_i$ を双方向に結んでいます。
長さ $N$ の順列 $P=(p_1,p_2,...,p_N)$ であって、以下の条件を満たすものの個数を $998244353$ で割った余りを求めてください。

• $1 \leq i,j \leq N,i \neq j$ をともに満たす全ての正整数の組 $(i,j)$ について、$| p_i-p_j | + dist(i,j)$ が偶数である。

ただし、$dist(i,j)$ は $T$ の頂点 $i$ から頂点 $j$ への最短経路に存在する辺の本数を表します。

制約

• $1\leq N \leq 200000$
• $1\leq u_i,v_i \leq N$
• 入力は全て整数
• 与えられるグラフは木である 　　

入力

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

出力

答えを出力してください。

入力例1

3
1 2
1 3

出力例1

2

$P$ として考えられるものは $6$ つありますが、そのうち $(2,1,3)$ と $(2,3,1)$ の $2$ つが条件を満たします。

入力例2

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

出力例2

445103186

答えを $998244353$ で割った余りを求めてください。