该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

对于以 $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)$（注意不是在当前树中连边，树只会一直进行删边操作，而共轭树图$G$只会一直进行加边操作）。

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

输入格式

第一行一个整数 $n$。

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

输出格式

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

输入输出样例 #1

输入 #1

4
1 4
2 3
3 4

输出 #1

2

输入输出样例 #2

输入 #2

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

输出 #2

4605

样例解释 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)\}$。

数据范围

• 对于 $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)：无特殊限制。