Score: $600$ points

问题陈述

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。 此外，还有 $N$ 个编号为 $1$ 到 $N$ 的物品。最初，物品 $i$ 放置在顶点 $i$ 上。 你可以执行以下操作任意次数，可能为零次：

• 选择一条边。设顶点 $u$ 和 $v$ 是边的端点，并交换顶点 $u$ 和 $v$ 上的物品。然后，删除所选的边。

设顶点 $i$ 上的物品为 $a_i$。当你完成操作时，存在多少种不同的可能序列 $(a_1, a_2, \dots, a_N)$？请计算出结果对 $998244353$ 取模后的值。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There is a tree with $N$ vertices numbered $1$ to $N$. The $i$-th edge connects vertices $u_i$ and $v_i$.
Additionally, there are $N$ pieces numbered $1$ to $N$. Initially, piece $i$ is placed on vertex $i$.
You can perform the following operation any number of times, possibly zero:

• Choose one edge. Let vertices $u$ and $v$ be the endpoints of the edge, and swap the pieces on vertices $u$ and $v$. Then, delete the chosen edge.

Let $a_i$ be the piece on vertex $i$. How many different possible sequences $(a_1, a_2, \dots, a_N)$ exist when you finish performing the operation? Find the count modulo $998244353$.

Constraints

• $2 \leq N \leq 3000$
• $1 \leq u_i \lt v_i \leq N$
• The graph given in the input is a tree.

Input

The input is given from Standard Input in the following format:

$N$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_{N-1}$ $v_{N-1}$

Output

Print the number, modulo $998244353$, of possible sequences $(a_1, a_2, \dots, a_N)$.

Sample Input 1

3
1 2
2 3

Sample Output 1

5

For example, the sequence $(a_1, a_2, a_3) = (2, 1, 3)$ can be obtained by the following steps:

• Choose the first edge, swap the pieces on vertices $1$ and $2$, and delete the edge. This results in $(a_1, a_2, a_3) = (2, 1, 3)$.
• Finish operating.

Also, the sequence $(a_1, a_2, a_3) = (3, 1, 2)$ can be obtained by the following steps:

• Choose the second edge, swap the pieces on vertices $2$ and $3$, and delete the edge. This results in $(a_1, a_2, a_3) = (1, 3, 2)$.
• Choose the first edge, swap the pieces on vertices $1$ and $2$, and delete the edge. This results in $(a_1, a_2, a_3) = (3, 1, 2)$.
• Finish operating.

The operation can yield the following five sequences:

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

Sample Input 2

5
2 5
3 4
1 3
1 5

Sample Output 2

34

Sample Input 3

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

Sample Output 3

799