Þetta er gagnvirkt dæmi.

Little Cyan Fish á einfalt óstefnt net með $n$ hnútum sem eru merktir frá $1$ til $n$ og $m$ leggjum sem eru merktir frá $1$ til $m$. Upphaflega er liturinn á hnút $i$ jafn $i$.

Tveir leikmenn, A og B, spila leik sem samanstendur af $m$ umferðum. Í hverri umferð gera leikmennirnir eftirfarandi í þessari röð:

• Leikmaður A velur legg $(u, v)$ sem hefur ekki verið valinn í neinni fyrri umferð.
• Leikmaður B velur annan endahnút þessa leggs og breytir lit hans í núverandi lit hins endahnútsins.

Eftir allar $m$ umferðirnar vinnur Leikmaður B ef allir hnútar hafa sama lit. Annars vinnur Leikmaður A.

Little Cyan Fish vill að þú ákvarðir hvor leikmaðurinn getur tryggt sér sigur óháð leikjum hins leikmannsins. Spilaðu síðan sem sá leikmaður á móti honum og vinndu leikinn.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T \le 10^4$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan tvær heiltölur $n$ og $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$), sem gefa til kynna fjölda hnúta annars vegar og fjölda leggja hins vegar.

Næstu $m$ línur lýsa leggjunum. $i$-ta línan af þessum línum inniheldur tvær heiltölur $u_i$ og $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), sem þýðir að leggur $i$ tengir saman hnúta $u_i$ og $v_i$.

Það er tryggt að netið hefur engar sjálfslykkjur eða margfalda leggi. Netið getur verið ótengt.

Það er tryggt að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^5$, og að summa $m$ yfir öll prófunartilvik fari ekki yfir $10^5$.

Eftir að hafa lesið inn net skaltu ljúka samskiptunum fyrir það prófunartilvik áður en næsta net er lesið inn.

Samskiptareglur

Til að velja hlutverk þitt skaltu skrifa út línu sem inniheldur A eða B. Skrifaðu út A ef Leikmaður A getur tryggt sér sigur, eða B ef Leikmaður B getur tryggt sér sigur. Little Cyan Fish mun spila sem hinn leikmaðurinn.

Spilaðu síðan nákvæmlega $m$ umferðir á eftirfarandi hátt.

• Ef þú spilar sem A skaltu skrifa út línu sem inniheldur eina heiltölu $e$ ($1 \le e \le m$), númer leggs sem hefur ekki verið valinn í neinni fyrri umferð. Sem svar færðu eina heiltölu $x$ á línu. Hnútur $x$ er endahnútur leggs $e$, og litur hans breytist í núverandi lit hins endahnútsins.
• Ef þú spilar sem B skaltu lesa eina heiltölu $e$ ($1 \le e \le m$) á línu, númer leggs sem hefur ekki verið valinn í neinni fyrri umferð. Skrifaðu út línu sem inniheldur eina heiltölu $x$, endahnút leggs $e$. Litur hnúts $x$ breytist í núverandi lit hins endahnútsins.

Eftir allar $m$ umferðirnar skaltu lesa eina heiltölu. Þessi heiltala er 1 ef þú valdir rétt hlutverk og vannst leikinn. Eftir að hafa fengið 1 skaltu halda áfram í næsta prófunartilvik. Eftir síðasta prófunartilvikið á forritið þitt að hætta keyrslu.

Gagnvirki prófarinn mun senda -1 ef þú velur rangt hlutverk, gerir ólöglegan leik eða tapar leik. Ef þú færð -1 á einhverjum tímapunkti á forritið þitt að hætta keyrslu samstundis.

Eftir að þú skrifar út hlutverk þitt eða leik, ekki gleyma að skrifa út nýlínustaf og tæma úttaksstrauminn (flush).

Prófunartól: Prófunartól er lagt til svo keppendur geti þróað og prófað lausnir sínar. Þú getur sótt þetta tól í viðhengjunum. Keyrðu tólið með valkostinum -h til að birta notkunarleiðbeiningar. Prófunartólið nær aðeins yfir hluta af þeim prófunaraðstæðum og eiginleikum sem studdir eru af opinbera gagnvirka prófaranum.

Examples

Input 1

2
3 2
2 3
1 2

1

2

1
4 3
1 2
2 3
3 4


2

4

3
1

Output 1

B

3

1






A
1

3

2

Note

Leikirnir tveir í dæminu eru sýndir hér að neðan. Í hverju skrefi velur A upplýsta legginn og B endurlitar hringlaga hnútinn. Brotalínuleggir voru valdir fyrr.