题目描述

$N$ 頂点からなる木が与えられます。頂点には $1$ から $N$ までの番号がついており、$i$ 番目の辺は頂点 $a_i$ と $b_i$ を結んでいます。

正整数列 $P\ =\ (P_1,\ P_2,\ \ldots,\ P_N)$ であって、以下の条件を満たすものの個数を $998244353$ で割った余りを求めてください。

• $1\leq\ P_i\leq\ N$
• $i\neq\ j$ ならば $P_i\neq\ P_j$
• $1\leq\ a,\ b,\ c\leq\ N$ に対して頂点 $a$ と 頂点 $b$、頂点 $b$ と頂点 $c$ がともに隣接しているならば、$P_a\ <\ P_b\ >\ P_c$ または $P_a\ >\ P_b\ <\ P_c$ が成り立つ。

输入格式

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

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

输出格式

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

题目大意

有一个 $n$ 个点的树，编号为 $1\sim n$，第 $i$ 条边连接 $a_i$ 和 $b_i$。

找出 $1\sim n$ 的排列 $p$ 的个数，满足对于任意 $1\le a,b,c\le n$，其中点 $a$ 和点 $b$ 相邻，点 $b$ 和点 $c$ 相邻，都有 $p_a<p_b>p_c$ 或 $p_a>p_b<p_c$。

对 $998244353$ 取模。

3
1 2
2 3

4

4
1 2
1 3
1 4

12

6
1 2
2 3
3 4
4 5
5 6

122

9
8 5
9 8
1 9
2 5
6 1
7 6
3 8
4 1

19080

提示

制約

• $2\leq\ N\leq\ 3000$
• $1\leq\ a_i,\ b_i\leq\ N$
• 入力されるグラフは木である

Sample Explanation 1

条件を満たす $P$ は以下の $4$ 通りです。 - $P\ =\ (1,\ 3,\ 2)$ - $P\ =\ (2,\ 1,\ 3)$ - $P\ =\ (2,\ 3,\ 1)$ - $P\ =\ (3,\ 1,\ 2)$