#585 All Falls Down

Loading problem...

Preparing the statement, recent submissions, and submit form.

#585 All Falls Down

Time limit: 1000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

Statement language

Alice and Bob are playing All Falls Down, a game in which two tokens fall down a tree. The board is a tree rooted at vertex $1$ , with each child placed below its parent.

First, Alice chooses two distinct vertices $u,v$ and places one token on each vertex.

Starting with Bob, the players then take turns. On a turn, the player must choose one child of the current vertex for each token and move both tokens simultaneously to the chosen children. In other words, both tokens must fall one level down. If either token cannot move farther down, the player whose turn it is loses.

Both players play optimally. Count the unordered pairs $\{u,v\}$ of distinct vertices for which Alice wins.

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $a_1\ b_1$ $a_2\ b_2$ $\vdots$ $a_{N-1}\ b_{N-1}$

For each $i$ , there is an edge between vertices $a_i$ and $b_i$ .

Output

For each case, print the number of vertex pairs for which Alice wins on its own line.

Constraints

$1\leq T\leq200\,000$ .
$1\leq N\leq200\,000$ .
$1\leq a_i,b_i\leq N$ ( $1\leq i\leq N-1$ ).
The given edges form a tree.
The sum of $N$ over all cases is at most $200\,000$ .

Subtasks

#	Score	Constraints
1	10	$N\leq8$ , and the sum of $N$ over all cases is at most $2000$ .
2	25	$N\leq2000$ , and the sum of $N$ over all cases is at most $2000$ .
3	20	The tree is a path, and vertex $1$ is an endpoint of the path.
4	45	No additional constraints.

Samples

Input

Output

In the first case, there is only one vertex, so no pair of distinct vertices can be chosen. The answer is $0$ .
In the second case, the only pair for which Alice wins is $\{1,2\}$ . The token at vertex $2$ cannot move down, so Bob loses on his first turn.
In the third case, the pairs for which Alice wins are $\{1,3\}$ and $\{2,3\}$ . Both pairs contain vertex $3$ , so Bob loses on his first turn. For the remaining pair $\{1,2\}$ , Bob moves the tokens to vertices $2$ and $3$ , respectively, and Alice loses on her next turn.
In the fourth case, the pairs for which Alice wins are $\{1,2\}$ , $\{1,3\}$ , $\{1,4\}$ , $\{2,3\}$ , $\{2,4\}$ , and $\{3,4\}$ . Every pair contains at least one vertex with no children, so Bob loses on his first turn.

Editorial

View editorial