頂点の高さ (paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

ここまでの問題では、辺が与えられる際にその辺が接続する頂点の親子関係が与えられていましたが、そのような情報が元々わかっていることは少なく、実際に根付き木を利用する際には、与えられた木と根の情報から自分で頂点の親子関係を求める必要があることが多いです。

根付き木の頂点・辺についての情報が与えられるので、木の全ての辺に対して、どのような親子関係になっているかを求めてください。

根の頂点を 1 つ決めると、各頂点の親子関係が定まります。
例えば、根を 1 としたときは上図のような関係に、6 としたときは下図のような関係になります。

ヒント
まずは、木の全ての頂点について根からの距離（最短の移動回数）を求めてみましょう。

入力される値

N R
a_1 b_1
...
a_{N-1} b_{N-1}

・1 行目には、根付き木の頂点の数 N, 根付き木の根の頂点番号 R が与えられます。
・続く N-1 行では、根付き木の各辺の両端の頂点の番号 a_i , b_i が与えられます。(1 ≦ i ≦ N-1)

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: ・合計で N-1 行出力してください。
・i 行目には、a_i が b_i の親である場合は "A" を、b_i が a_i の親である場合は "B" を出力してください。(1 ≦ i ≦ N-1)

条件: すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ N ≦ 100
・ 1 ≦ R ≦ N
・ 1 ≦ a_i , b_i ≦ N (1 ≦ i ≦ N-1)

入力例1: 10 1
1 2
1 3
2 4
5 3
6 3
7 3
5 8
9 5
7 10

出力例1: A
A
A
B
B
B
A
B
A

入力例2: 10 6
1 2
1 3
2 4
5 3
6 3
7 3
5 8
9 5
7 10

出力例2: A
B
A
B
A
B
A
B
A

問題一覧へ戻る