Game on a Tree#11279
Alice and Bob play a game on a tree. Initially, all nodes are white.
Alice is the first to move. She chooses any node and puts 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 cannotmove the chip loses.
Who wins the game?
An ancestor of a node in a rooted tree is any node on the path between and the root of the tree.
A descendant of a node in a rooted tree is any node such that node is located on the path between and the root of the tree.
We consider that the root of the tree is .
The first line contains one integer (1 \le n \le 10^5) - the number of nodes.
Each of the next n - 1 lines contains two integers and (1 \le u, v \le n) - the edges of the tree. It is guaranteed that they form a tree.
In a single line, print "Alice" (without quotes), if Alice wins. Otherwise, print "Bob".
Example 1
Example 2
In the first test case, the tree is a straight line and has nodes, so Bob can always choose the last white node.
In the second test case, the optimal strategy for Alice is to place the chip on . This node will become black. Bob has to choose the node . Alice can choose any of , , or . Bob can only choose . Alice chooses any of the white sons of , and Bob cannot make a move.