Magnetic Path - Repovive Starter Round 4 | Repovive

15F. Magnetic Path

3000 pts2s256 MB

You are given a tree with $n$ vertices, numbered from $1$ to $n$ .

There are two pieces of iron. Initially, one of them is on vertex $1$ , and the other one is on vertex $n$ .

In one operation, you choose a vertex $v$ and place a magnet on it for one second. During this second, each piece of iron behaves independently:

if the piece is already on vertex $v$ , it does not move;
otherwise, it moves by one edge along the unique simple path from its current vertex to $v$ .

After that, the magnet is removed.

A sequence of operations is successful if after all operations both pieces of iron are on the same vertex.

Among all successful sequences with the minimum possible number of operations, count how many different sequences exist. Two sequences are considered different if for some operation position, the chosen magnet vertices are different.

Output the answer modulo $998244353$ .

If the two pieces of iron are already on the same vertex, the empty sequence is considered the only optimal sequence.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
The given graph is a tree
The distance between vertices $1$ and $n$ is even

Input

t

\left. \begin{array}{l} n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

3
1 2
2 3

Case 3

Case 4

Case 5

Explanation

Case 1

The two pieces are already on the same vertex, so no operation is needed. The empty sequence is the only optimal sequence.

Case 2

One operation is necessary. Choosing vertex 2 moves both pieces to vertex 2, so there is exactly one optimal sequence.

Case 3

One operation is necessary. Choosing vertex 2 or vertex 3 moves both pieces to vertex 2, so there are two optimal sequences.

Case 4

Two operations are necessary. The first magnet can be placed on one of vertices 2, 3, 4, 5, 6. After that, the second magnet can be placed on one of vertices 3, 5, 6. Hence there are 15 optimal sequences.

Case 5

Three operations are necessary. The numbers of possible choices in the three operations are 7, 5, and 1, respectively, so the answer is 35.

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given a tree with $n$ vertices, numbered from $1$ to $n$ .

There are two pieces of iron. Initially, one of them is on vertex $1$ , and the other one is on vertex $n$ .

In one operation, you choose a vertex $v$ and place a magnet on it for one second. During this second, each piece of iron behaves independently:

if the piece is already on vertex $v$ , it does not move;
otherwise, it moves by one edge along the unique simple path from its current vertex to $v$ .

After that, the magnet is removed.

A sequence of operations is successful if after all operations both pieces of iron are on the same vertex.

Output the answer modulo $998244353$ .

If the two pieces of iron are already on the same vertex, the empty sequence is considered the only optimal sequence.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
The sum of $n$ over all test cases is at most $2 \times 10^5$
The given graph is a tree
The distance between vertices $1$ and $n$ is even

t

\left. \begin{array}{l} n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

15F. Magnetic Path

Constraints

Input

Output

Samples

15F. Magnetic Path

Constraints

Input

Output

Samples