Problem Description

Alice and Bob are playing a game on a tree. Initially, all nodes on the tree are white.

Alice starts first. She can choose any node and place a marker on it, turning that node black. After that, the players take turns. In each turn, a player can move the marker from its current node to any white ancestor or child node and turn the destination node black. The player who cannot make a move loses the game.

Who will win the game?

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

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

The root of the tree is node $1$.

Input Format

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

The next $n-1$ lines each contain two integers $u$ and $v \ (1 \leq u, v \leq n)$, representing an edge $(u, v)$ in the tree. The data guarantees that these edges will form a tree.

Output Format

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

Sample Input and Output

Sample Input #1

4
1 2
2 3
3 4

Sample Output #1

Bob

Sample Input #2

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

Sample Output #2

Alice

Notes

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

In the second sample, Alice's best strategy is to place the marker on node $3$, which then turns black. Bob can only move the marker to node $1$. Alice can choose to move to node $4, 5, 6,$ or $7$. Bob can only choose node $2$. Alice then chooses any white child node of $2$, and Bob cannot move.

见题面 Input 部分

见题面 Output 部分