Alice and Bob are playing a game with a tree with n nodes. Alice always plays first, and the two players move in alternating turns.
Before the game starts, they pick a vertex as the root of the tree. After that, the game begins. The game's rules are as follows:
You can assume that each player plays optimally, meaning they will not make a move that causes them to lose the game if some better, winning move exists.
Now Alice wants to know how many vertices are there in the tree such that if they pick it as the initial root, she would always win the game. Can you help her to find it?
The first line has an integer T (1 ≤ T ≤ 10) which describes the number of test scenarios. Then T tests follow.
Each test has one integer at the first line N (2 ≤ N ≤ 100000). The next N-1 lines each contains two integers X, Y (1 ≤ X, Y ≤ N; X != Y). This means that there is an edge between vertex X and vertex Y.
The tree is always valid.
For each test case, print the case number at the first line as "Case t:" where t is the test case number, followed by the number of such vertices.
Input | Output |
---|---|
1 3 1 2 2 3 | Case 1: 2 |
Suppose 1 is the root of the tree. In that case, Alice can pick the sub-tree rooted at vertex number 2 in her first move. Then the only choice for Bob is to pick vertex 3. After that, the game ends. As Bob made the last move, Alice wins the game.
Suppose 3 is the root of the tree. Again Alice will win the game by picking the sub-tree rooted at vertex 2 in her first move.
Suppose 2 is the root of the tree. Now Alice can pick either vertex 1 or Vertex 3. In either way, the game will end as soon as Alice makes her first move and she will lose the game.
So Alice can win the game if vertex 1 or vertex 3 is picked as the initial root.