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

DFS Good Pairs - Repovive Premier Round 3 | Repovive

6F. DFS Good Pairs

3000 pts2s256 MB

You are given a tree with $n$ vertices. The tree is rooted at vertex $1$ .

A DFS order of the tree is the order in which vertices are first visited by a depth-first search starting from vertex $1$ . The children of each vertex may be visited in any order.

For an ordered pair $(i,j)$ with $1 \le j < i \le n$ , call the pair good if there exists a DFS order of the tree such that vertex $i$ is the $i$ -th vertex in the order, and vertex $j$ appears before vertex $i$ in that order.

Count the number of good pairs.

$1 \le t \le 10^4$
$1 \le n \le 5000$
The sum of $n$ over all test cases is at most $5000$

Constraints

$1 \le t \le 10^4$
$1 \le n \le 5000$
The sum of $n$ over all test cases is at most $5000$

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

Case 3

Case 4

Case 5

Explanation

Case 1

The DFS orders are $(1,2,4,3)$ and $(1,3,2,4)$ . Vertex $3$ is never the third vertex, so no pair of the form $(3,j)$ is good. Vertex $2$ can be second after vertex $1$ . Vertex $4$ can be fourth after all smaller vertices. Therefore the good pairs are $(2,1)$ , $(4,1)$ , $(4,2)$ , and $(4,3)$ .

Case 2

The DFS orders are $(1,2,4,5,3)$ , $(1,2,5,4,3)$ , $(1,3,2,4,5)$ , and $(1,3,2,5,4)$ . Vertex $3$ is never the third vertex. Vertex $4$ can be fourth in $(1,3,2,4,5)$ , where vertices $1$ , $2$ , and $3$ are before it. Vertex $5$ can be fifth in $(1,3,2,4,5)$ , where all smaller vertices are before it. Together with $(2,1)$ , this gives $8$ good pairs.

Case 3

Vertex $4$ is never the fourth vertex. Vertex $3$ can be third, for example in $(1,2,3,4,5,6)$ , but then among smaller vertices only vertex $1$ is before it. Vertex $5$ can be fifth after all smaller vertices, for example in $(1,3,4,2,5,6)$ . Vertex $6$ can be sixth after all smaller vertices, for example in $(1,3,4,2,5,6)$ . Therefore the answer is $1+1+4+5=11$ .

Case 4

The DFS orders are $(1,2,4,5,3,6)$ , $(1,2,5,4,3,6)$ , $(1,3,6,2,4,5)$ , and $(1,3,6,2,5,4)$ . Vertex $3$ is never the third vertex. Vertex $4$ can be fourth only in orders starting with $(1,3,6,2)$ , so only vertices $1$ and $2$ may be smaller vertices before it. Vertex $5$ can be fifth with vertices $1$ , $2$ , and $3$ before it. Vertex $6$ can be sixth after all smaller vertices, for example in $(1,2,4,5,3,6)$ . Together with $(2,1)$ , this gives $11$ good pairs.

Case 5

Every DFS order starts by completely visiting either the subtree of vertex $2$ or the subtree of vertex $3$ . Therefore vertices $4$ and $5$ are never in their own numbered positions. Vertex $6$ can be sixth after all smaller vertices, for example in $(1,2,4,5,3,6,7)$ . Vertex $7$ can be seventh after all smaller vertices, for example in $(1,2,4,5,3,6,7)$ . Together with $(2,1)$ , this gives $12$ good pairs.

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given a tree with $n$ vertices. The tree is rooted at vertex $1$ .

A DFS order of the tree is the order in which vertices are first visited by a depth-first search starting from vertex $1$ . The children of each vertex may be visited in any order.

Count the number of good pairs.

$1 \le t \le 10^4$
$1 \le n \le 5000$
The sum of $n$ over all test cases is at most $5000$

$1 \le t \le 10^4$
$1 \le n \le 5000$
The sum of $n$ over all test cases is at most $5000$

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

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

6F. DFS Good Pairs

Constraints

Input

Output

Samples

6F. DFS Good Pairs

Constraints

Input

Output

Samples