We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. Deforestation

Deforestation

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:

  1. They move in alternating turns, and both players always move optimally.
  2. 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.
  3. The first player to be unable to make a move loses the game.
  4. Alice always makes the first move.

For example, the diagram below shows a tree of size , where the root is node : tree-initial.png

Now, if a player removes the edge between and , then nodes and become disconnected from the root and are removed from the game:

tree-removed.png

Given the structure of the tree, determine and print the winner of the game. If Alice wins, print ; otherwise print .

Input Format

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 .

Constraints

Output Format

For each test case, print the name of the winner (i.e., or ) on a new line.

Sample Input

1
5
1 2
3 1
3 4
4 5

Sample Output

Alice

Explanation

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.