Alice and Bob Game on Rooted Trees

Alice and Bob are playing a game on a forest consisting of n nodes and m edges (0 ≤ m ≤ n − 1). The edges form several rooted trees. In each connected component the root is defined as the vertex with the smallest number.

The rules of the game are as follows. In each turn the current player selects any node x that has not been deleted and deletes x along with all of its ancestors in the tree. (Note that the tree structure remains even if some nodes are deleted, i.e. the parent–child relationships are not updated.) The player who cannot make a move loses.

The two players take turns and play optimally. Determine whether there is a winning strategy for the first player.

Note: When a node is deleted, its children (if still available) remain in the game with their original parent pointers intact even if the parent has been deleted. For example, consider a chain 1–3–2, where node 1 is the root. If node 1 is deleted, node 3 is still considered the parent of node 2.

Game theory background: This game can be analyzed using Sprague–Grundy theory. For each tree, define a function g(v) as the Grundy number for a subtree rooted at node v. When a move is made by selecting a node, say by choosing a chain of nodes from the root to some node x, the resulting game state is a disjoint sum of the subgames corresponding to the remaining branches. In our solution, we recursively determine g(v) using the following idea.

For a node v with children, define:

• S(v) = XOR over all children u of g(u).
• For each node u, define H(u) = g(u) ⊕ S(u).
• Let M(v) be the set of values obtainable by taking the XOR along any chain starting from one of v's children. Formally, M(v) is defined recursively as
  M(v) = { 0 } ∪ { H(u) ⊕ r : for any child u of v and every r ∈ M(u) }.
• Then define the set of options for node v as
  F(v) = { S(v) ⊕ r : r ∈ M(v) }.
• Finally, the Grundy number at v is
  g(v) = mex( F(v) ),
  and define H(v) = g(v) ⊕ S(v).

The overall game is a disjunctive sum of the trees. Let the nim‐sum be
X = ⊕ (g(root) of each tree).

If X ≠ 0 then the first player (Alice) has a winning strategy; otherwise Bob wins.

inputFormat

The first line contains two integers n and m – the number of nodes and the number of edges.

Each of the next m lines contains two integers u and v indicating that there is an edge between nodes u and v.

It is guaranteed that the edges form a forest. (Note that when m=0 each node is an isolated tree.)

outputFormat

Print a single line with the string Alice if the first player has a winning strategy; otherwise, print Bob.

sample

3 2
1 2
2 3

Bob

</p>