這是一道互動題。

小青魚有一張包含 $n$ 個頂點和 $m$ 條邊的簡單無向圖，頂點編號為 $1$ 到 $n$，邊編號為 $1$ 到 $m$。最初，頂點 $i$ 的顏色為 $i$。

兩位玩家 A 和 B 玩一個包含 $m$ 輪的遊戲。在每一輪中，兩位玩家按順序執行以下操作：

• 玩家 A 選擇一條在先前的任何一輪中都未被選擇過的邊 $(u, v)$。
• 玩家 B 選擇這條邊的一個端點，並將其顏色修改為另一個端點當前的顏色。

在全部 $m$ 輪結束後，如果所有頂點的顏色都相同，則玩家 B 獲勝。否則，玩家 A 獲勝。

小青魚希望你判斷哪位玩家可以無論對手如何操作都保證獲勝。然後作為該玩家與他對局並贏得遊戲。

輸入格式

本題有多組測試資料。輸入的第一行包含一個整數 $T$（$1 \le T \le 10^4$），表示測試資料的組數。

對於每組測試資料，第一行包含兩個整數 $n$ 和 $m$（$2 \le n \le 10^5$，$1 \le m \le 10^5$），分別表示頂點的數量和邊的數量。

接下來 $m$ 行描述各條邊。其中第 $i$ 行包含兩個整數 $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$。

在讀入一張圖後，請先完成該組測試資料的互動，再讀入下一張圖。

互動

為了選擇你的角色，請輸出一行，包含 A 或 B。如果玩家 A 可以保證獲勝則輸出 A，如果玩家 B 可以保證獲勝則輸出 B。小青魚將扮演另一位玩家。

然後按如下方式進行恰好 $m$ 輪遊戲。

• 如果你扮演 A，輸出一行一個整數 $e$（$1 \le e \le m$），表示一條在先前的任何一輪中都未被選擇過的邊的編號。作為回應，你將在一行中讀入一個整數 $x$。頂點 $x$ 是邊 $e$ 的一個端點，且它的顏色被修改為另一個端點當前的顏色。
• 如果你扮演 B，在一行中讀入一個整數 $e$（$1 \le e \le m$），表示一條在先前的任何一輪中都未被選擇過的邊的編號。輸出一行一個整數 $x$，表示邊 $e$ 的一個端點。頂點 $x$ 的顏色將被修改為另一個端點當前的顏色。

在全部 $m$ 輪結束後，讀入一個整數。如果你選擇了正確的角色並贏得了遊戲，該整數為 1。收到 1 後，請繼續處理下一組測試資料。在最後一組測試資料結束後，你的程式應當終止。

如果你選擇了錯誤的角色、進行了不合法的操作，或者輸掉了遊戲，互動器將傳送 -1。如果你在任意時刻收到 -1，你的程式應當立即終止。

在輸出你的角色或操作後，請不要忘記輸出換行符並重新整理輸出緩衝區（flush）。

測試工具： 題目提供了一個測試工具，以幫助選手開發和測試自己的程式。你可以從附件中下載該工具。使用 -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

說明

範例中的兩局遊戲如下所示。在每一步中，A 選擇高亮顯示的邊，B 將畫圈的頂點重新染色。虛線邊表示在先前已經被選擇過的邊。