AT_code_thanks_festival_2015_f お祭りとお菓子

$A$ 和 $B$ 君参加了一个节日活动。 在活动中，他们获得了一种由 $N$ 个果实和 $N-1$ 根枝条构成的甜点。果实的编号从 $1$ 到 $N$，枝条的编号从 $1$ 到 $N-1$。枝条 $i$（$1 \le i \le N-1$）连接果实 $s_i$ 和 $t_i$。而果实 $1$ 与其他所有果实通过这些枝条是连通的。这意味着，对于每个满足 $2 \le X \le N$ 的整数 $X$，都存在一个序列 $a_{X,1}, \ldots, a_{X,k}$（满足 $k \ge 1$ 且 $1 \le a_{X,i} \le N-1$）满足以下条件： - 序列中的第一根枝条 $a_{X,1}$ 连接的果实中有果实 $1$。 - 对于任何一个满足 $1 \le i \le k-1$ 的整数 $i$，枝条 $a_{X,i}$ 和 $a_{X,i+1}$ 连接的果实之间有共享的果实。 - 序列中的最后一根枝条 $a_{X,k}$ 连接的果实中有果实 $X$。 $A$ 和 $B$ 从 $A$ 开始轮流选择并吃掉一个果实和其直接连接的所有枝条。在每一回合，他们只能选择连接枝条数不超过一根的果实进行吃掉。连接有两根或更多枝条的果实在当前回合无法被吃掉，否则会弄得满嘴黏糊。 果实 $1$ 非常美味，所以两人都希望能够在自己回合中吃到果实 $1$。 在双方都采取最佳策略时，最终谁会吃到果实 $1$ 呢？

输入如下所示： > $N$ > $s_1$ $t_1$ > $s_2$ $t_2$ > ... > $s_{N-1}$ $t_{N-1}$ - 第一行是整数 $N$，表示果实的数量，满足 $2 \le N \le 100,000$。 - 接下来的 $N-1$ 行，每行有两个整数 $s_i$ 和 $t_i$，表示枝条 $i$ 连接果实 $s_i$ 和果实 $t_i$。

如果 $A$ 能先吃到果实 $1$，输出 `A`；如果 $B$ 能吃到，输出 `B`。请在输出的最后加上一个换行符。 ### 示例解释 1 假设 $A$ 先吃掉果实 $4$。然后 $B$ 可以选择吃的果实有 $2$, $5$, $6$。 - 如果 $B$ 吃掉果实 $2$，那么 $A$ 可以直接吃掉果实 $1$。 - 如果 $B$ 选择吃掉果实 $5$，随后 $A$ 吃掉果实 $6$，$B$ 在下一回合会被迫吃掉果实 $2$ 或 $3$，然后 $A$ 就可以吃果实 $1$。 - 如果 $B$ 吃了果实 $6$，接着 $A$ 吃掉果实 $5$，然后 $B$ 只能吃掉果实 $2$ 或 $3$。这样 $A$ 也能吃到果实 $1$。 通过最佳策略，$A$ 可以吃到果实 $1$。 ### 示例解释 2 $A$ 可以直接选择吃掉果实 $1$。 **本翻译由 AI 自动生成**

### Sample Explanation 1 最初に $ A $ さんが実 $ 4 $ を食べたとします。このとき、$ B $ さんが食べられる実は実 $ 2 $, $ 5 $, $ 6 $ のいずれかです。 - $ B $ さんが実 $ 2 $ を食べたならば、直後に $ A $ さんが実 $ 1 $ を食べることができます。 - $ B $ さんが実 $ 5 $ を食べたならば、直後に $ A $ さんが実 $ 6 $ を食べる選択をとったときに、次の手番で $ B $ さんは実 $ 2 $ か実 $ 3 $ を食べることになり、その直後 $ A $ さんが実 $ 1 $ を食べることができます。 - $ B $ さんが実 $ 6 $ を食べたならば、直後に $ A $ さんが実 $ 5 $ を食べる選択をとったときに、次の手番で $ B $ さんは実 $ 2 $ か実 $ 3 $ を食べることになり、その直後 $ A $ さんが実 $ 1 $ を食べることができます。 以上より両者が最善を尽くしたときに実 $ 1 $ を食べることができるのは $ A $ さんです。 ### Sample Explanation 2 最初に $ A $ さんが実 $ 1 $ を食べることができます。