题目描述

有一棵 $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$ 取模的结果。

样例 1

输入

3
1 2
2 3

输出

5

样例 2

输入

5
2 5
3 4
1 3
1 5

输出

34

样例 3

输入

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

输出

799

说明/提示

限制条件

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