Alice and Bob are playing a game with a rooted tree. The tree has vertices and the first node, , is always the root. Here are the basic rules:
They move in alternating turns, and both players always move optimally.
During each move, a player removes an edge from the tree, disconnecting one of its leaves or branches. The leaf or branch that was disconnected from the rooted tree is removed from the game.
The first player to be unable to make a move loses the game.
Alice always makes the first move.
For example, the diagram below shows a tree of size , where the root is node :
Now, if a player removes the edge between and , then nodes and become disconnected from the root and are removed from the game:
Given the structure of the tree, determine and print the winner of the game. If Alice wins, print ; otherwise print .
The first line contains a single integer, , denoting the number of test cases.
For each test case, the first line contains an integer, , denoting the number of nodes in the tree.
Each of the subsequent lines contains space-separated integers, and , defining an edge connecting nodes and .
For each test case, print the name of the winner (i.e., or ) on a new line.
Test Case 0:
Alice removes the edge connecting node to node , effectively trimming nodes and from the tree. Now the only remaining edges are and . Because Bob can't remove both of them, Alice will make the last possible move. Because the last player to move wins, we print on a new line.