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.

#### Input

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 × 10^{5}), indicating the number of vertices in the tree.

Each of the following `n` - 1 lines contains two integers `u` and `v` (1 ≤ `u`, `v` ≤ `n`), 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 × 10^{5}. 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 × 10^{4}.

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++.

#### Output

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

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

#### Sample Output

8
2

#### Hint

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