{"raw_statement":[{"iden":"statement","content":"Alice and Bob play a game on a tree. Initially, all nodes are white. \n\nAlice is the first to move. She chooses any node and put a chip on it. The node becomes black. After that players take turns. In each turn, a player moves the chip from the current position to an ancestor or descendant node, as long as the node is not black. This node also becomes black. The player who cannot move the chip looses.\n\nWho wins the game?\n\nAn _ancestor_ of a node $v$ in a rooted tree is any node on the path between $v$ and the root of the tree.\n\nA _descendant_ of a node $v$ in a rooted tree is any node $w$ such that node $v$ is located on the path between $w$ and the root of the tree.\n\nWe consider that the root of the tree is $1$.\n\nThe first line contains one integer $n$ ($1 <= n <= 100 thin 000$) — the number of nodes.\n\nEach of the next $n -1$ lines contains two integers $u$ and $v$ ($1 <= u, v <= n$) — the edges of the tree. It is guaranteed that they form a tree.\n\nIn a single line, print \"_Alice_\" (without quotes), if Alice wins. Otherwise, print \"_Bob_\".\n\nIn the first test case, the tree is a straight line and has $4$ nodes, so Bob always can choose the last white node.\n\nIn the second test case, the optimal strategy for Alice is to place the chip on $3$. This node will become black. Bob has to choose the node $1$. Alice can choose any of $4$, $5$, $6$, or $7$. Bob can only choose $2$. Alice chooses any of the white sons of $2$, and Bob cannot make a move.\n\n"},{"iden":"input","content":"The first line contains one integer $n$ ($1 <= n <= 100 thin 000$) — the number of nodes.Each of the next $n -1$ lines contains two integers $u$ and $v$ ($1 <= u, v <= n$) — the edges of the tree. It is guaranteed that they form a tree."},{"iden":"output","content":"In a single line, print \"_Alice_\" (without quotes), if Alice wins. Otherwise, print \"_Bob_\"."},{"iden":"examples","content":"Input4\n1 2\n2 3\n3 4\nOutputBobInput7\n2 1\n2 6\n1 3\n2 5\n7 2\n2 4\nOutputAlice"},{"iden":"note","content":"In the first test case, the tree is a straight line and has $4$ nodes, so Bob always can choose the last white node.In the second test case, the optimal strategy for Alice is to place the chip on $3$. This node will become black. Bob has to choose the node $1$. Alice can choose any of $4$, $5$, $6$, or $7$. Bob can only choose $2$. Alice chooses any of the white sons of $2$, and Bob cannot make a move."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the initial number of cupcakes, with $ 1 \\leq n \\leq 10^9 $.  \nPlayers: Mahmoud (first), Bashar (second).  \nOn each turn, a player must eat exactly 1 cupcake.  \nA player loses if, at the start of their turn, exactly 1 cupcake remains.\n\n**Constraints**  \n- Players alternate turns, starting with Mahmoud.  \n- Each player plays optimally.  \n- Only legal move: reduce cupcake count by 1.  \n\n**Objective**  \nDetermine the winner:  \nIf the number of turns before the losing state (1 cupcake) is odd, Mahmoud wins; if even, Bashar wins.  \n\nThe game ends when a player faces 1 cupcake.  \nThe number of moves until the end is $ n - 1 $.  \nMahmoud wins if $ n - 1 $ is even → $ n $ is odd.  \nBashar wins if $ n - 1 $ is odd → $ n $ is even.  \n\nThus:  \n$$\n\\text{Winner} = \n\\begin{cases}\n\\text{Mahmoud} & \\text{if } n \\equiv 1 \\pmod{2} \\\\\n\\text{Bashar} & \\text{if } n \\equiv 0 \\pmod{2}\n\\end{cases}\n$$","simple_statement":"Mahmoud and Bashar take turns eating cakes. On each turn, a player must eat exactly 1 cake. The player who faces exactly 1 cake left loses. Mahmoud goes first. Given n cakes, who wins if both play optimally?","has_page_source":false}