Game on a Tree#1180
Alice and Bob are playing a game on an undirected tree. Alice moves first and, on her turn, can mark any vertex of the tree. Then, the players alternate turns. On each turn, a player can mark a vertex adjacent to the last marked vertex that has not been previously marked. A player cannot mark an already marked vertex. If a player cannot mark a vertex, that player loses.
Assuming both players play optimally, determine the winner from the initial state of the game.
The first line contains , the number of test cases. Then the descriptions of the test cases follow.
The first line of each test case contains , the number of vertices in the tree.
Each of the next N - 1 lines contains two space-separated integers and , indicating that there is an edge between and (1 \leq a, b \leq N).
It is known that T \leq 25, N \leq 50000.
Output lines, one for each test case. Output "Alice" if Alice wins the game, or "Bob" otherwise. [Do not print the quotes].
Example 1