Problem Description

There is a tree with $n$ nodes. A subset $S$ of all simple paths in the tree is called good if and only if:

• Every edge of the tree is covered by exactly one path in $S$.
• Among all sets that satisfy the first condition, the maximum number of times any node appears as an endpoint of a path in $S$ is minimized.

Count the number of good sets $S$. Output the answer modulo $998244353$.

Input Format

Each test file contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 2\cdot 10^4$), the number of test cases. For each test case:

• The first line contains an integer $n$ ($2 \leq n \leq 10^5$), the number of nodes in the tree.
• The next $n - 1$ lines each contain two integers $u$ and $v$ ($1 \leq u, v \leq n$), indicating an edge between node $u$ and node $v$.

It is guaranteed that all given edges form a tree. It is also guaranteed that, for a single test file, the sum of all $n$ does not exceed $2\cdot 10^5$.

Output Format

For each test case, output one integer per line: the number of good sets $S$ modulo $998244353$.

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

1
9
45

Hint

For the first test case, the only possible $S$ that satisfy the first condition are $\{(1, 2), (2, 3)\}$ and $\{(1, 3)\}$. Since in $\{(1, 3)\}$ the maximum number of occurrences of any node as an endpoint is $1$, while in $\{(1, 2), (2, 3)\}$ it is $2$, only $\{(1, 3)\}$ is good.

Translated by ChatGPT 5