AT_arc130_d.[ARC130D] Zigzag Tree

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

请输出答案。

限制条件

• $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 翻译