题目描述

给定一棵有 $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}$

输出格式

请输出答案。

样例 1

输入

3
1 2
2 3

输出

4

样例 2

输入

4
1 2
1 3
1 4

输出

12

样例 3

输入

6
1 2
2 3
3 4
4 5
5 6

输出

122

样例 4

输入

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$
• 输入的图是一棵树

样例解释 1

满足条件的 $P$ 有以下 $4$ 种：

• $P = (1, 3, 2)$
• $P = (2, 1, 3)$
• $P = (2, 3, 1)$
• $P = (3, 1, 2)$

由 ChatGPT 4.1 翻译