Problem Description

Mr. A and Ms. B are attending a festival.

At the festival, they received a sweet made of $ N $ fruits and $ N-1 $ branches. The fruits are numbered from $ 1 $ to $ N $, and the branches are numbered from $ 1 $ to $ N-1 $. Branch $i\ (1\ ≦\ i\ ≦\ N-1)$ connects fruit $ s_i $ and fruit $ t_i $. Also, fruit $ 1 $ is connected to any other fruit through branches. That is, for all integers $ X $ satisfying $2\ ≦\ X\ ≦\ N$, there exists a sequence $ a_{X,1} $, ... , $ a_{X,k} $ ($k\ ≧\ 1$ and $1\ ≦\ i\ ≦\ k$ for any integer $ i $ satisfying $1\ ≦\ a_{X,i}\ ≦\ N-1$) that satisfies the following conditions:

• Branch $ a_{X,1} $ connects fruit $ 1 $.
• For any integer $ i $ satisfying $1\ ≦\ i\ ≦\ k-1$, there is a fruit common to the fruits connected by branch $ a_{X,i} $ and branch $ a_{X,i+1} $.
• Branch $ a_{X,k} $ connects fruit $ X $.

Mr. A and Ms. B will eat the fruits and branches alternately, starting with Mr. A. In their turn, either Mr. A or Ms. B will choose a fruit that is connected to at most one branch, and eat that fruit along with all the branches directly connected to it. Fruits connected to two or more branches are difficult to eat at that moment, and trying to eat them would make their mouths sticky.

Since fruit $ 1 $ is particularly delicious, both Mr. A and Ms. B will try to eat fruit $ 1 $ on their turn if possible.

When both play optimally, who will end up eating fruit $ 1 $?

Input Format

The input is given from the standard input in the following format:

$ N $ $ s_1 $ $ t_1 $ $ s_2 $ $ t_2 $ : $ s_{N-1} $ $ t_{N-1} $

• The first line contains the number of fruits $N\ (2\ ≦\ N\ ≦\ 100,000)$.
• The next $ N-1 $ lines contain information about the branches. The $i\ (1\ ≦\ i\ ≦\ N-1)$-th line contains two integers $ s_i $, $t_i\ (1\ ≦\ s_i\ ＜\ t_i\ ≦\ N)$ separated by a space, indicating that branch $ i $ connects fruit $ s_i $ and fruit $ t_i $.

Output Format

Output A if Mr. A eats fruit $ 1 $, or B if Ms. B eats fruit $ 1 $. End the output with a newline.

Sample Input and Output

Sample Input #1

6
1 2
1 3
2 4
3 5
3 6

Sample Output #1

A

Sample Input #2

5
1 2
2 3
2 4
2 5

Sample Output #2

A

Sample Input #3

9
1 2
1 3
1 4
3 5
4 6
4 7
7 8
7 9

Sample Output #3

B

Notes/Hints

Sample Explanation 1

If Mr. A eats fruit $ 4 $ first, Ms. B can then eat fruit $ 2 $, $ 5 $, or $ 6 $. - If Ms. B eats fruit $ 2 $, Mr. A can immediately eat fruit $ 1 $. - If Ms. B eats fruit $ 5 $, Mr. A can choose to eat fruit $ 6 $ next, and then Ms. B would have to eat either fruit $ 2 $ or $ 3 $, after which Mr. A can eat fruit $ 1 $. - If Ms. B eats fruit $ 6 $, Mr. A can choose to eat fruit $ 5 $ next, and then Ms. B would have to eat either fruit $ 2 $ or $ 3 $, after which Mr. A can eat fruit $ 1 $. Therefore, when both play optimally, Mr. A can eat fruit $ 1 $.

Sample Explanation 2

Mr. A can eat fruit $ 1 $ first.

见题面 Input 部分

见题面 Output 部分