これはインタラクティブな問題です。

Little Cyan Fish は、$1$ から $n$ までの番号がついた $n$ 個の頂点と、$1$ から $m$ までの番号がついた $m$ 本の辺からなる単純無向グラフを持っています。最初、頂点 $i$ の色は $i$ です。

2 人のプレイヤー A と B が、$m$ ラウンドからなるゲームを行います。各ラウンドでは、プレイヤーたちは以下の操作を順番に行います。

• プレイヤー A は、これまでのどのラウンドでも選ばれていない辺 $(u, v)$ を 1 つ選ぶ。
• プレイヤー B は、この辺の端点を 1 つ選び、その色をもう一方の端点の現在の色に変更する。

全 $m$ ラウンドの終了後、すべての頂点が同じ色であればプレイヤー B の勝ちです。そうでなければ、プレイヤー A の勝ちです。

Little Cyan Fish は、相手の行動にかかわらずどちらのプレイヤーが確実に勝てるかをあなたに判定してほしいと思っています。その後、そのプレイヤーとして彼と対戦し、ゲームに勝利してください。

入力

複数のテストケースがあります。入力の 1 行目には、テストケースの個数を表す単一の整数 $T$ ($1 \le T \le 10^4$) が与えられます。

各テストケースについて、1 行目には頂点の個数と辺の本数をそれぞれ表す 2 つの整数 $n$ と $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$) が与えられます。

続く $m$ 行には辺の情報が与えられます。これらのうち $i$ 行目には 2 つの整数 $u_i$ と $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$) が与えられ、辺 $i$ が頂点 $u_i$ と頂点 $v_i$ を結んでいることを意味します。

グラフに自己ループや多重辺がないことが保証されます。グラフは非連結である可能性があります。

すべてのテストケースにわたる $n$ の総和は $10^5$ を超えず、すべてのテストケースにわたる $m$ の総和も $10^5$ を超えないことが保証されます。

1 つのグラフを読み込んだ後、次のグラフを読み込む前にそのテストケースのインタラクションを完了させてください。

インタラクション

あなたの役割を選ぶため、A または B を含む 1 行を出力してください。プレイヤー A が確実に勝てる場合は A を、プレイヤー B が確実に勝てる場合は B を出力してください。Little Cyan Fish はもう一方のプレイヤーとしてプレイします。

その後、以下の通りにちょうど $m$ ラウンドをプレイしてください。

• あなたが A としてプレイする場合、これまでのどのラウンドでも選ばれていない辺の番号を表す単一の整数 $e$ ($1 \le e \le m$) を含む 1 行を出力してください。その返答として、1 行に単一の整数 $x$ が与えられます。頂点 $x$ は辺 $e$ の端点であり、その色はもう一方の端点の現在の色に変更されます。
• あなたが B としてプレイする場合、これまでのどのラウンドでも選ばれていない辺の番号を表す単一の整数 $e$ ($1 \le e \le m$) を 1 行から読み込んでください。辺 $e$ の端点を表す単一の整数 $x$ を含む 1 行を出力してください。頂点 $x$ の色は、もう一方の端点の現在の色に変更されます。

全 $m$ ラウンドの終了後、単一の整数を読み込んでください。あなたが正しい役割を選び、かつゲームに勝利した場合、この整数は 1 です。1 を受け取った後、次のテストケースに進んでください。最後のテストケースの終了後、あなたのプログラムは終了しなければなりません。

誤った役割を選んだ場合、不正な手を打った場合、またはゲームに負けた場合、ジャッジプログラムは -1 を送ります。いずれかの時点で -1 を受け取った場合、あなたのプログラムは直ちに終了しなければなりません。

役割や手を出力した後は、改行文字を出力し、出力ストリームをフラッシュすることを忘れないでください。

テストツール： 参加者が解答を開発・テストするのを支援するため、テストツールが提供されています。このツールは添付ファイルからダウンロードできます。使用方法を表示するには、-h オプションを付けてツールを実行してください。このテストツールは、公式のジャッジプログラムがサポートするテストシナリオおよび機能の一部のみをカバーしています。

入出力例

入力 1

2
3 2
2 3
1 2

1

2

1
4 3
1 2
2 3
3 4


2

4

3
1

出力 1

B

3

1






A
1

3

2

注記

サンプルの 2 つのゲームを以下に示します。各ステップにおいて、A は強調表示された辺を選び、B は丸で囲まれた頂点の色を塗り替えます。破線の辺はそれ以前に選ばれた辺です。