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