问题描述

$A$ 和 $B$ 参加了一个祭典。

他们在祭典上收到了一份由 $N$ 个果实和 $N-1$ 条枝组成的糖果。每个果实都有编号从 $1$ 到 $N$，而每条枝都有编号从 $1$ 到 $N-1$。枝 $i (1 \leq i \leq N-1)$ 连接着果实 $s_i$ 和果实 $t_i$。此外，它与果实 $1$ 以及其他任何果实都通过一条或多条枝连接。也就是说，对于满足 $2 \leq X \leq N$ 的所有整数 $X$，存在一个序列 $a_{X,1}$, ... , $a_{X,k}$ ($k \geq 1$，对于满足 $1 \leq i \leq k$ 的所有整数 $i$ 都有 $1 \leq a_{X,i} \leq N-1$)，该序列满足以下条件：

• 枝 $a_{X,1}$ 连接着果实 $1$。
• 对于满足 $1 \leq i \leq k-1$ 的任意整数 $i$，枝 $a_{X,i}$ 连接着的果实和枝 $a_{X,i+1}$ 连接着的果实至少有一个共同的果实。
• 枝 $a_{X,k}$ 连接着果实 $X$。

$A$ 和 $B$ 将交替选择并食用果实和枝。在他们的回合中，$A$ 或 $B$ 可以选择只连接了 $1$ 条或更少枝的果实，并同时食用该果实以及与该果实直接相连的所有枝。连接了 $2$ 条或更多枝的果实在当前时刻还不能被食用，如果强行尝试食用，嘴巴会变得黏黏的。

此外，由于果实 $1$ 特别好吃，$A$ 和 $B$ 都会在自己的回合中采取行动，以便能够吃到果实 $1$。

当双方尽力而为时，到底是哪个人将吃到果实 $1$ 呢？

输入

输入以以下格式从标准输入获取。

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

• 第 $1$ 行包含果实数量 $N (2 \leq N \leq 100,000)$。
• 第 $2$ 行到第 $N-1$ 行提供了有关枝的信息。其中的第 $i (1 \leq i \leq N-1)$ 行包含了两个整数 $s_i$, $t_i (1 \leq s_i ＜ t_i \leq N)$，用空格分隔。这表示枝 $i$ 连接着果实 $s_i$ 和果实 $t_i$。

输出

如果 $A$ 吃到了果实 $1$，则输出字符 A；如果 $B$ 吃到了果实 $1$，则输出字符 B。输出末尾包含换行符。

示例1

6
1 2
1 3
2 4
3 5
3 6

输出示例1

A

我们假设 $A$ 先吃掉果实 $4$。这样，$B$ 可以选择吃掉果实 $2$、$5$ 或者 $6$。

• 如果 $B$ 吃掉了果实 $2$，那么紧接着 $A$ 可以吃掉果实 $1$。
• 如果 $B$ 吃掉了果实 $5$，那么在下一轮中，$B$ 将选择吃掉果实 $2$ 或者 $3$，然后紧接着 $A$ 可以吃掉果实 $1$。
• 如果 $B$ 吃掉了果实 $6$，那么在下一轮中，$B$ 将选择吃掉果实 $2$ 或者 $3$，然后紧接着 $A$ 可以吃掉果实 $1$。

由此可见，当双方都尽力而为时，只有 $A$ 可以吃到果实 $1$。

示例2

5
1 2
2 3
2 4
2 5

输出示例2

A

$A$ 可以在开始时吃掉果实 $1$。

示例3

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

输出示例3

B