/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
A さんと B さんはお祭りに参加しています。
お祭りで N 個の実と N-1 本の枝からなるお菓子をもらいました。実には 1 から N までの番号が付けられており、枝には 1 から N-1 までの番号が付けられています。枝 i (1 ≦ i ≦ N-1) は実 s_i と実 t_i を結んでいます。また、実 1 と他のどの実についても、枝を介して連結です。すなわち、2 ≦ X ≦ N を満たすすべての整数 X について、ある数列 a_{X,1}, ... , a_{X,k} (k ≧ 1 かつ 1 ≦ i ≦ k を満たすどの整数 i についても 1 ≦ a_{X,i} ≦ N-1) が存在し、その数列は以下の条件を満たします。
- 枝 a_{X,1} が結ぶ実に実 1 がある。
- 1 ≦ i ≦ k-1 を満たす任意の整数 i に関して、枝 a_{X,i} が結ぶ実と枝 a_{X,i+1} が結ぶ実に共通して登場する実がある。
- 枝 a_{X,k} が結ぶ実に実 X がある。
A さんと B さんは、A さんから始めて交互に実や枝を食べていきます。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 ≦ N ≦ 100,000) が与えられる。
- 2 行目から N-1 行には、枝に関する情報が与えられる。このうち i (1 ≦ i ≦ N-1) 行目には 2 つの整数 s_i, t_i (1 ≦ s_i ＜ t_i ≦ N) が空白区切りで与えられる。これは枝 i が実 s_i と実 t_i を結んでいることを表す。
出力
A さんが実 1 を食べる場合は文字 A を、B さんが実 1 を食べる場合は文字 B を 1 行に出力せよ。出力の末尾にも改行を入れること。
入力例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 を食べたならば、直後に A さんが実 6 を食べる選択をとったときに、次の手番で B さんは実 2 か実 3 を食べることになり、その直後 A さんが実 1 を食べることができます。
- B さんが実 6 を食べたならば、直後に A さんが実 5 を食べる選択をとったときに、次の手番で B さんは実 2 か実 3 を食べることになり、その直後 A さんが実 1 を食べることができます。
以上より両者が最善を尽くしたときに実 1 を食べることができるのは A さんです。
入力例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