Description

Alice and Bob play a game on a tree. At the beginning, all nodes on the tree are white.

Alice moves first. She may choose any node and place a token on it, and that node becomes black. After that, the players take turns. In each turn, the current player may move the token from its current node to a white ancestor of that node or to a white child of that node, and the node moved to becomes black. The player who cannot make a move loses.

In a rooted tree, an ancestor of a node $v$ is any node on the path from the root to node $v$.

In a rooted tree, a child of a node $v$ is a node $w$ such that $v$ is on the path from the root to $w$ and $v$ is the parent of $w$.

The root of the tree is node $1$.

Input Format

The first line contains an integer $n \ (1 \leq n \leq 100 \ 000)$, the number of nodes in the tree.

Each of the next $n-1$ lines contains two integers $u$ and $v \ (1 \leq u, v \leq n)$, denoting an edge $(u, v)$ of the tree. The testdata guarantees that these edges form a tree.

Output Format

Output one line. If Alice wins the game, output Alice; otherwise, output Bob.

4
1 2
2 3
3 4

Bob

7
2 1
2 6
1 3
2 5
7 2
2 4

Alice

Hint

In the first sample, the tree is a chain of $4$ nodes, so Bob can always move the token to the last remaining white node.

In the second sample, Alice’s best strategy is to place the token on node $3$ first, and then node $3$ becomes black. Bob can only move the token to node $1$. Alice can choose node $4, 5, 6$ or $7$ to move to. Bob can then only choose node $2$. After Alice chooses any white child of node $2$, Bob will have no move.

Translated by ChatGPT 5