Optimal Leaf‐Plucking Tree Game

Two players, A and B, play a turn‐based game on a rooted tree. The tree has node 1 as its root. At the start, the tree contains at least one leaf. In each turn the current player must choose a nonempty set of leaf nodes (nodes with no children) and remove them from the tree. (Note that the player may remove any number of leaves available in that turn, but cannot choose to pass.) When some leaves are removed the parent nodes – if they no longer have any children – become new leaves and will be available for removal in subsequent turns.

The game proceeds in alternate turns: player A makes the first move, then player B, and so on. The twist is that the player who removes node 1 (the root) wins the game. (Observe that node 1 is never a leaf initially; it becomes a leaf only when all of its children have been removed.)

Both players play optimally. Your task is to decide, given the tree, which player will eventually win.

Game analysis – An equivalent misère‐subtraction game on branches

One may show that the game can be seen as a disjunctive sum of games played on the branches attached directly to the root. For each child v of node 1, let f(v) be defined as the maximum depth in the subtree rooted at v (where the root 1 is at depth 1). In the branch corresponding to v the number of forced moves if played one‐by‐one is f(v) - 1. In a chain (that is, if the branch is just a simple path) the only possible move is to remove the unique leaf – which decreases the “move‐count” by 1. Hence a chain with an even number of moves (i.e. when f(v)-1 is even) is a winning “subgame” for the mover, while if f(v)-1 is odd the mover loses if forced to play in that branch.

When node 1 has exactly one child the outcome is determined solely by that branch: player A wins if and only if f(v)-1 is even. However, when node 1 has two or more children the players have extra freedom: on each turn a player may choose a nonempty subset of the currently available leaves (possibly coming from different branches) to remove. In other words, the players are effectively playing a misère version of a multi‐heap subtraction game in which the “heap” corresponding to a child v has size f(v)-1, with the extra twist that removing the last heap (i.e. making node 1 a leaf) gives the win to the opponent (because the opponent then removes node 1 on his turn).

It turns out that the winning condition is as follows:

• If node 1 has no children (i.e. the tree consists solely of the root) then player A wins.
• If node 1 has exactly one child v then A wins if and only if f(v)-1 is even; otherwise B wins.
• If node 1 has at least two children and in each branch the available move‐count is 1 (i.e. for every child v we have f(v)-1 = 1), then A wins if and only if the number of children is even; otherwise B wins.
• If node 1 has at least two children and at least one branch has f(v)-1 > 1, then if the XOR (taken in the usual sense on nonnegative integers) of all values f(v)-1 (over all children v of node 1) is nonzero, then A wins; otherwise B wins.

You are to implement a program that decides the winner given the tree.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10^5), the number of nodes of the tree.

Each of the following n−1 lines contains two integers u and v (1 ≤ u, v ≤ n), denoting an edge between nodes u and v. It is guaranteed that these edges form a tree with node 1 as the root.

outputFormat

Output a single character: A if player A (the first player) wins under optimal play, or B otherwise.

sample

2
1 2

B