Minimum Number of Guards

You are given a collection of villages connected by roads such that the villages form a tree (i.e. a connected acyclic graph). The problem is to determine the minimum number of guards required, where a single guard placed at the optimal position can cover villages within a certain range. The key observation is that the optimal placement is at the center of the tree’s diameter. In other words, if the tree diameter is \(D\), then the minimum number of guards required is \(\lceil D/2 \rceil\).

Note: A tree with a single village requires no guards.

Input Format: The first line contains an integer \(T\), the number of test cases. Each test case begins with an integer \(n\), the number of villages. If \(n > 1\), the next \(n-1\) lines each contain two integers \(u\) and \(v\), representing a bidirectional road between villages \(u\) and \(v\).

Output Format: For each test case, output a single integer on a new line representing the minimum number of guards needed.

inputFormat

The input is read from standard input and has the following structure:

T
n
u1 v1
u2 v2
... (n-1 lines if n > 1)
... (next test cases)

Where:

• T is the number of test cases.
• For each test case, n is the number of villages. For \(n > 1\), the following \(n-1\) lines describe the roads between villages as pairs of integers \(u\) and \(v\).

outputFormat

For each test case, print one integer per line representing the minimum number of guards required.

## sample

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

0
1
1
2

</p>