LP and Rifleman

题目描述

LP and Rifleman are playing a game.

Initially, there is an unrooted tree with $n$ vertices.

Two players, LP and Rifleman, play alternately. LP moves first.

1. LP chooses a vertex whose degree is not equal to 2 and removes it, or she may do nothing.

2. Then Rifleman chooses two vertices that are not connected (i.e., belong to different connected components) and adds an edge between them.

If after a non-zero number of operations , the graph becomes connected again, the game ends immediately.

LP wants to minimize the number of remaining vertices, Rifleman wants to maximize it. Determine the final number of vertices when both play optimally.

输入格式

The first line contains the number of testcases $T(1\leq T\leq 10^5)$ .

For each testcase, the first line contains the number of vertices $n(1\leq \sum n\leq 10^6)$.

Each for the next $n-1$ lines contains two integers $u$ and $v$ ,meaning that there is an edge between vertex $u$ and $v$.

输出格式

For each testcase,you need to print the final number of vertices in a single line.

样例输入 #1

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

样例输出 #1

2
3

样例输入 #2

2
7
1 2
1 3
2 4
2 5
3 6
3 7
12
1 2
1 3
1 4
1 5
2 6
2 7
2 8
2 9
3 10
3 11
3 12

样例输出 #2

3
4