You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

E.Space 有 $n$ 个 AI 连接形成一个树形结构，后面忘了。

题目描述

有一棵 $n$ 个点的树，第 $i$ 条边连接节点 $u_i$ 和节点 $v_i$。第 $i$ 个点有一个权值 $a_i$，初始 $a_i = 0$。

依次对每个 $t = 1, 2, \ldots, (n-1)$ 有如下事件发生：若 $a_{u_t} = a_{v_t} = 0$，则选择 仅一个 $x \in \{u_t, v_t\}$，让 $a_x \gets t$。

请统计所有操作过后，可能存在的不同的序列 $a$ 的个数。因为答案可能很大，所以请对 $998244353$ 取模。

输入格式

从 mis.in 中读入数据。

本题单个测试点内有多组数据。

第一行，一个整数 $t$，描述数据组数。对于每组数据：

• 第一行，一个整数 $n$。
• 接下来 $n - 1$ 行，第 $i$ 行有两个整数 $u_i, v_i$。

输出格式

输出到 mis.out 中。

对于每组数据，输出一行一个整数，表示答案对 $998244353$ 取模后的结果。

样例

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

4
10
28

样例 1 解释

对于第一组数据，有以下 $4$ 种可能的序列：$[1, 0, 0, 0]$，$[2, 1, 0, 0]$，$[3, 2, 1, 0]$，$[0, 2, 1, 3]$。

对于第二组数据，有以下 $10$ 种可能的序列：$[0, 1, 0, 0, 4, 2, 5]$，$[0, 1, 0, 0, 6, 0, 2]$，$[0, 1, 0, 0, 6, 2, 4]$，$[0, 1, 0, 5, 4, 2, 0]$，$[0, 1, 6, 0, 0, 0, 2]$，$[0, 1, 6, 0, 0, 2, 4]$，$[0, 3, 0, 0, 6, 0, 1]$，$[0, 3, 6, 0, 0, 0, 1]$，$[3, 0, 0, 0, 6, 0, 1]$，$[3, 0, 6, 0, 0, 0, 1]$。

附加样例

见 下发 的 mis/mis2.in 和 mis/mis2.ans 至 mis/mis12.in 和 mis/mis12.ans。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（10 pts）：$t = 1$，$n \leq 12$。
• Subtask 2（15 pts）：树是一条链。
• Subtask 3（25 pts）：每个点的度数不超过 $5$。
• Subtask 4（50 pts）：无特殊限制。

对于所有数据，保证 $1 \leq t \leq 2\times 10^4$，$\sum n \leq 3\times 10^5$，$n \geq 2$，$1 \leq u_i, v_i \leq n$，保证输入构成一棵树。