Welcome to ZOJ
147 - The 17th Zhejiang University Programming Contest Sponsored by TuSimple - B
Edge to the Root

Time Limit: 1 Second      Memory Limit: 131072 KB

Given a tree with n vertices, we want to add an edge between vertex 1 and vertex x, so that the sum of d(1, v) for all vertices v in the tree is minimized, where d(u, v) is the minimum number of edges needed to pass from vertex u to vertex v. Do you know which vertex x we should choose?

Recall that a tree is an undirected connected graph with n vertices and n - 1 edges.


There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains an integer n (1 ≤ n ≤ 2 × 105), indicating the number of vertices in the tree.

Each of the following n - 1 lines contains two integers u and v (1 ≤ u, vn), indicating that there is an edge between vertex u and v in the tree.

It is guaranteed that the given graph is a tree, and the sum of n over all test cases does not exceed 5 × 105. As the stack space of the online judge system is not very large, the maximum depth of the input tree is limited to about 3 × 104.

We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.


For each test case, output a single integer indicating the minimum sum of d(1, v) for all vertices v in the tree (NOT the vertex x you choose).

Sample Input

1 2
2 3
3 4
3 5
3 6
1 2
2 3

Sample Output



For the first test case, if we choose x = 3, we will have

d(1, 1) + d(1, 2) + d(1, 3) + d(1, 4) + d(1, 5) + d(1, 6) = 0 + 1 + 1 + 2 + 2 + 2 = 8

It's easy to prove that this is the smallest sum we can achieve.

Submit    Status