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

$ curl repovive.com/contests/6/problems/F

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

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

$ curl repovive.com/contests/6/problems/F

Repovive

DFS Good Pairs - Repovive Premier Round 3 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

6F. DFS Good Pairs

3000 ptstype :zen to enter zen mode

Time: 2sMemory: 256 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