Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

A Boring Game

By nfssdq · Limits 1s, 512 MB

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:

  • In a single move, a player can pick a vertex u which is not the root of the tree. (If someone picks the root, the whole tree will be gone and they will be very upset!)
  • After choosing u, the player will keep the sub-tree under u and will delete every other vertex.
  • u will be the root of the new tree and the other player will make his/her move. The game continues until someone is unable to make a move (when there is only one vertex left).
  • The person who made the last move loses the game.

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?

Input

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.

Output

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.

Sample

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


Discussion
Statistics

69% Solution Ratio

Neri_KuttaEarliest, Feb '17

sarwarITFastest, 0.1s

Uniquepro.Lightest, 393 kB

rubbyEShortest, 407B

Submit

Login to submit