no tags

Input:
The first line contains the number of test cases T. T test cases follow. The first line contains N, the number of cities in Byteland. The cities are numbered 0..N - 1. The following N - 1 lines contain the description of the roads. The ith line contains two integers a_i and b_i, meaning that there is a road connecting cities with numbers a_i and b_i.
Output:
Output T lines, one corresponding to each test case containing the required answer for that test case.
Constraints:
1 <= T <= 20
1 <= N <= 10000
0 <= a_i,b_i < N
Sample Input:
3
4
0 1
0 2
0 3
6
0 1
1 2
2 3
2 4
4 5
7
0 1
1 2
2 3
2 4
4 5
3 6
Sample Output:
1
1
2
Explanation:
For the first case, one robot is enough to repair all roads: (0,1) -> (0,2) -> (0,3)
For the second case, one robot is again enough: (0,1) -> (1,2) -> (2,3) -> (2,4) -> (4,5)
The the third case, there is no way to repair all the roads with one robot and at least two are needed.

Input:

The first line contains the number of test cases T. T test cases follow. The first line contains N, the number of cities in Byteland. The cities are numbered 0..N - 1. The following N - 1 lines contain the description of the roads. The ith line contains two integers a_i and b_i, meaning that there is a road connecting cities with numbers a_i and b_i.

Output:

Output T lines, one corresponding to each test case containing the required answer for that test case.

Constraints:

1 <= T <= 20

1 <= N <= 10000

0 <= a_i,b_i < N

Sample Input:

3

4

0 1

0 2

0 3

6

0 1

1 2

2 3

2 4

4 5

7

0 1

1 2

2 3

2 4

4 5

3 6

Sample Output:

1

1

2

Explanation:

For the first case, one robot is enough to repair all roads: (0,1) -> (0,2) -> (0,3)

For the second case, one robot is again enough: (0,1) -> (1,2) -> (2,3) -> (2,4) -> (4,5)

The the third case, there is no way to repair all the roads with one robot and at least two are needed. Pluston: 2012-02-19 18:16:44 Is it necessary for the bot to start at 0th city? biQar: 2011-10-18 20:53:55 nice problem Jalan !