- Prepare
- Algorithms
- Game Theory
- Deforestation

# 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:

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

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