Alice and Bob’s Tree Game

Alice and Bob play a game on a rooted tree. Initially, all nodes in the tree are white. The tree is rooted at node \(1\). In the very first move, Alice may choose any node and place a marker on it; that node becomes black. Then the players take turns. In each turn, the current player must move the marker from its current node \(v\) to a white node \(u\) that is either an ancestor or a descendant of \(v\) (note that in a rooted tree, a node \(u\) is called an ancestor of \(v\) if \(u\) lies on the unique path from the root to \(v\), and \(u\) is called a descendant of \(v\) if \(v\) lies on the unique path from the root to \(u\)). When the marker is moved to \(u\), that node becomes black. A player who cannot make a move loses the game.

Your task is to decide who wins the game under optimal play. Since Alice may choose any node as the starting position, if there exists at least one initial move by which she can force a win, then Alice wins; otherwise Bob wins.

Note: All formulas must be rendered in LaTeX. For example, the condition for \(u\) to be an ancestor of \(v\) is rendered as \(\text{in}[u] \le \text{in}[v] \le \text{out}[u]\), where \(\text{in}[\cdot]\) and \(\text{out}[\cdot]\) are the entering and leaving times of the nodes in a DFS order.

inputFormat

The first line contains an integer \(n\) (the number of nodes in the tree). The next \(n-1\) lines each contain two integers \(u\) and \(v\) (\(1 \le u, v \le n\)) indicating that there is an edge between nodes \(u\) and \(v\). The tree is rooted at node \(1\). It is guaranteed that \(n\) is small (e.g. \(n \le 15\)) so that a state search using bitmask dynamic programming is feasible.

outputFormat

Output a single line: Alice if Alice can force a win with an appropriate choice of the initial marked node; otherwise, output Bob.

sample

1

Alice