AT_arc171_c [ARC171C] Swap on Tree

有一棵 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。 此外，有 $N$ 个编号为 $1$ 到 $N$ 的棋子。初始时，棋子 $i$ 放在顶点 $i$ 上。 你可以进行如下操作，任意次（包括 $0$ 次）： - 选择一条边。设该边的两个端点为顶点 $u$ 和 $v$，交换放在顶点 $u$ 和顶点 $v$ 上的棋子。然后，删除这条被选中的边。 设操作全部结束后，顶点 $i$ 上的棋子为 $a_i$。问作为数列 $(a_1, a_2, \dots, a_N)$ 可能出现的方案有多少种？请输出方案数对 $998244353$ 取模的结果。

输入以如下格式从标准输入读入。 > $N$ > $u_1$ $v_1$ > $u_2$ $v_2$ > $\vdots$ > $u_{N-1}$ $v_{N-1}$

输出作为 $(a_1, a_2, \dots, a_N)$ 可能出现的方案数对 $998244353$ 取模的结果。

## 限制条件 - $2 \leq N \leq 3000$ - $1 \leq u_i < v_i \leq N$ - 输入给出的图为一棵树 ## 样例解释 1 例如，可以通过以下步骤得到 $(a_1, a_2, a_3) = (2, 1, 3)$。 - 选择第 $1$ 条边，交换顶点 $1$ 和顶点 $2$ 上的棋子，并删除该边。此时 $(a_1, a_2, a_3) = (2, 1, 3)$。 - 结束操作。 又如，可以通过以下步骤得到 $(a_1, a_2, a_3) = (3, 1, 2)$。 - 选择第 $2$ 条边，交换顶点 $2$ 和顶点 $3$ 上的棋子，并删除该边。此时 $(a_1, a_2, a_3) = (1, 3, 2)$。 - 选择第 $1$ 条边，交换顶点 $1$ 和顶点 $2$ 上的棋子，并删除该边。此时 $(a_1, a_2, a_3) = (3, 1, 2)$。 - 结束操作。 通过操作可以得到的数列共有以下 $5$ 种： - $(1, 2, 3)$ - $(1, 3, 2)$ - $(2, 1, 3)$ - $(2, 3, 1)$ - $(3, 1, 2)$ 由 ChatGPT 4.1 翻译