#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/8/problems/d

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/8/problems/d

Repovive

Back

Code

Upload

Submissions

Learn

8D. Random Traversal

2000 ptstype :zen to enter zen mode

by Hamid Shafi

Time: 2sMemory: 256 MB

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

A random traversal is performed as follows.

At the beginning, only vertex $1$ is visited. Then, while there is at least one unvisited vertex, we choose uniformly at random one unvisited vertex that has at least one visited neighbor, and visit it.

Let $p_1, p_2, \ldots, p_n$ be the order in which the vertices are visited.

An inversion in this order is a pair $(i,j)$ such that $1 \le i < j \le n$ and $p_i > p_j$ .

Find the expected number of inversions in the visiting order.

Since the answer can be a rational number, output it modulo $998244353$ . More formally, if the expected value is equal to $\frac{P}{Q}$ , where $Q$ is not divisible by $998244353$ , output $P \cdot Q^{-1}$ modulo $998244353$ .

Constraints

$1 \le t \le 100$
$1 \le n \le 5000$
The sum of $n$ over all test cases is at most $5000$
The given graph is a tree

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

3
1 3
3 2

Case 4

Case 5

Explanation

Case 1

Only vertex $1$ is visited, so there is no pair of vertices.

Case 2

The visiting order is always $1, 2, 3$ , so there is no inversion.

Case 3

The visiting order is always $1, 3, 2$ . The pair of vertices $2$ and $3$ is inverted.

Case 4

After visiting vertex $1$ , the vertices $2$ , $3$ , and $4$ are visited in a uniformly random order. Among the three pairs of these vertices, each pair is inverted with probability $\frac{1}{2}$ , so the expected value is $\frac{3}{2}$ .

Case 5

Vertices $2$ and $3$ are both available after visiting vertex $1$ . The pair $2,3$ contributes $\frac{1}{2}$ . Vertex $4$ can only become available after vertex $3$ is visited, so the pair $2,4$ contributes $\frac{1}{4}$ . The expected value is $\frac{3}{4}$ .

Output

Case 1

Case 2

Case 3

Case 4

499122178

Case 5

249561089

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

A random traversal is performed as follows.

Let $p_1, p_2, \ldots, p_n$ be the order in which the vertices are visited.

An inversion in this order is a pair $(i,j)$ such that $1 \le i < j \le n$ and $p_i > p_j$ .

Find the expected number of inversions in the visiting order.

$1 \le t \le 100$
$1 \le n \le 5000$
The sum of $n$ over all test cases is at most $5000$
The given graph is a tree

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

Only vertex $1$ is visited, so there is no pair of vertices.

The visiting order is always $1, 2, 3$ , so there is no inversion.

The visiting order is always $1, 3, 2$ . The pair of vertices $2$ and $3$ is inverted.

Random Traversal - Repovive Standard Round 3 | Repovive | Repovive