共轭树图

题目信息

时间限制: 1s

空间限制: 512M

输入文件: reflection.in

输出文件: reflection.out

题目描述

对于以 $n$ 为根的有根树 $T$，保证 $T$ 中每个节点的父节点编号一定大于自身的编号。将 $T$ 的边编号为 $1, \ldots, n-1$，可通过如下方式生成 $T$ 的共轭树图 $G$：

• 选择 $1, \ldots, n-1$ 的一个排列 $p_1, \ldots, p_{n-1}$；
• 依次考虑 $i=1, \ldots, n-1$；
• 删除编号为 $p_i$ 的边，设其端点分别为 $a, b$，选择当前树中分别与 $a, b$ 连通的编号最大的点 $u, v$，在 $G$ 中连接边 $(u, v)$。

对于树 $T$，总共可能生成出多少种不同共轭树图 $G$ 呢？答案对 998244353 取模。

输入格式

第一行一个整数 $n$。

接下来 $n-1$ 行，每行两个整数 $a, b$，表示一条树边。

输出格式

一行一个整数表示答案对 998244353 取模的结果。

样例

样例输入 1

4
1 4
2 3
3 4

样例输出 1

2

样例解释 1

令第 $i$ 条输入的边编号为 $i$。

当 $p$ 为 $\{1,3,2\}$ 或 $\{3,1,2\}$ 或 $\{3,2,1\}$ 时会生成 $E(G)=\{(1,4),(2,3),(3,4)\}$。

另外三种 $p$ 会生成 $E(G)=\{(1,4),(2,4),(3,4)\}$。

样例输入 2

11
1 4
2 6
3 11
4 6
5 6
6 7
7 9
8 9
9 10
10 11

样例输出 2

4605

数据范围与提示

• 对于 $100 \%$ 的数据: $1 \leq n \leq 3 \times 10^3$。
• Subtask 1 (24 pts): $n \leq 5$;
• Subtask 2 (16 pts): $n \leq 14$;
• Subtask 3 (8 pts): $n \leq 10^3$，所有其他结点与 $n$ 直接相连；
• Subtask 4 (8 pts): $n \leq 10^3$， 树的形态为一条链；
• Subtask 5 (22 pts): $n \leq 50$;
• Subtask 6 (22 pts)：无特殊限制。