Game on a Tree
Alice and Bob are playing a game on an undirected Tree. Alice plays first. In first move, Alice can mark any vertex of the tree. After first move, they will play alternatively and each player will choose a vertex which is adjacent to the LAST marked vertex and mark it. Note that a player cannot mark a vertex which was already marked in a previous move. If a player can not choose any vertex, he or she loses.
Given that both players play optimally, can you find out who will win, even before the game begins.
Input
First line contains T, the number of test cases. Then description of each test case follows. First line contains a number N, the number of vertices in a tree. The next N-1 lines contains two space separated integers a b represents an undirected edge from a to b. (1 ≤ a, b ≤ N).
It is known that T ≤ 25, N ≤ 50000.
Output
Output T lines, each containing the answer for one test case. Output "Alice" if Alice wins the game, or "Bob" otherwise. [quotes for clarity only].