Detta är ett interaktivt problem.

Little Cyan Fish har en enkel oriktad graf med $n$ hörn numrerade från $1$ till $n$ och $m$ kanter numrerade från $1$ till $m$. Från början är färgen på hörn $i$ lika med $i$.

Två spelare, A och B, spelar ett spel som består av $m$ rundor. I varje runda utför spelarna följande handlingar i ordning:

• Spelare A väljer en kant $(u, v)$ som inte har valts i någon tidigare runda.
• Spelare B väljer en ändpunkt på denna kant och ändrar dess färg till den andra ändpunktens nuvarande färg.

Efter alla $m$ rundor vinner Spelare B om alla hörn har samma färg. Annars vinner Spelare A.

Little Cyan Fish vill att du avgör vilken spelare som kan garantera en vinst oavsett motståndarens drag. Spela sedan som den spelaren mot honom och vinn spelet.

Indata

Det finns flera testfall. Den första raden i indatan innehåller ett enda heltal $T$ ($1 \le T \le 10^4$), som anger antalet testfall.

För varje testfall innehåller den första raden två heltal $n$ och $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$), som anger antalet hörn respektive antalet kanter.

De följande $m$ raderna beskriver kanterna. Den $i$-te av dessa rader innehåller två heltal $u_i$ och $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), vilket betyder att kant $i$ förbinder hörnen $u_i$ och $v_i$.

Det garanteras att grafen inte har några öglor eller multipelkanter. Grafen kan vara osammanhängande.

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^5$, och att summan av $m$ över alla testfall inte överstiger $10^5$.

Efter att ha läst in en graf ska du slutföra interaktionen för det testfallet innan du läser in nästa graf.

Interaktionsprotokoll

För att välja din roll, skriv ut en rad som innehåller A eller B. Skriv ut A om Spelare A kan garantera en vinst, eller B om Spelare B kan garantera en vinst. Little Cyan Fish kommer att spela som den andra spelaren.

Spela sedan exakt $m$ rundor enligt följande.

• Om du spelar som A, skriv ut en rad som innehåller ett enda heltal $e$ ($1 \le e \le m$), indexet för en kant som inte har valts i någon tidigare runda. Som svar får du ett enda heltal $x$ på en rad. Hörn $x$ är en ändpunkt på kant $e$, och dess färg ändras till den andra ändpunktens nuvarande färg.
• Om du spelar som B, läs in ett enda heltal $e$ ($1 \le e \le m$) på en rad, indexet för en kant som inte har valts i någon tidigare runda. Skriv ut en rad som innehåller ett enda heltal $x$, en ändpunkt på kant $e$. Färgen på hörn $x$ ändras till den andra ändpunktens nuvarande färg.

Efter alla $m$ rundor, läs in ett enda heltal. Detta heltal är 1 om du valde rätt roll och vann spelet. Efter att ha mottagit 1, fortsätt med nästa testfall. Efter det sista testfallet ska ditt program avslutas.

Interaktorn skickar -1 om du väljer fel roll, gör ett ogiltigt drag eller förlorar ett spel. Om du tar emot -1 vid något tillfälle ska ditt program avslutas omedelbart.

Efter att du har skrivit ut din roll eller ett drag, glöm inte att skriva ut ett radbrytningstecken och tömma utmatningsbufferten (flush).

Testverktyg: Ett testverktyg tillhandahålls för att hjälpa tävlande att utveckla och testa sina lösningar. Du kan ladda ner detta verktyg från bilagorna. Kör verktyget med flaggan -h för att visa användningsinstruktioner. Testverktyget täcker endast några av de testscenarier och funktioner som stöds av den officiella interaktorn.

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

De två spelen i exemplet visas nedan. I varje steg väljer A den markerade kanten och B färgar om det inringade hörnet. Streckade kanter valdes tidigare.