Dette er en interaktiv oppgave.

Little Cyan Fish har en enkel urettet graf med $n$ noder nummerert fra $1$ til $n$ og $m$ kanter nummerert fra $1$ til $m$. Til å begynne med er fargen til node $i$ lik $i$.

To spillere, A og B, spiller et spill som består av $m$ runder. I hver runde utfører spillerne følgende handlinger i rekkefølge:

• Spiller A velger en kant $(u, v)$ som ikke har blitt valgt i noen tidligere runde.
• Spiller B velger ett endepunkt på denne kanten og endrer fargen til den nåværende fargen til det andre endepunktet.

Etter alle $m$ rundene vinner Spiller B hvis alle nodene har samme farge. Ellers vinner Spiller A.

Little Cyan Fish vil at du skal avgjøre hvilken spiller som kan garantere seier uavhengig av motspillerens trekk. Spill deretter som denne spilleren mot ham og vinn spillet.

Inndata

Det er flere testtilfeller. Den første linjen i inndataene inneholder et enkelt heltall $T$ ($1 \le T \le 10^4$), som angir antall testtilfeller.

For hvert testtilfelle inneholder den første linjen to heltall $n$ og $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$), som angir henholdsvis antall noder og antall kanter.

De neste $m$ linjene beskriver kantene. Den $i$-te av disse linjene inneholder to heltall $u_i$ og $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), som betyr at kant $i$ forbinder nodene $u_i$ og $v_i$.

Det er garantert at grafen ikke har løkker eller parallelle kanter. Grafen kan være usammenhengende.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $10^5$, og at summen av $m$ over alle testtilfeller ikke overstiger $10^5$.

Etter å ha lest inn en graf, må du fullføre interaksjonen for dette testtilfellet før du leser inn neste graf.

Interaksjonsprotokoll

For å velge rollen din, skriv ut en linje som inneholder A eller B. Skriv ut A hvis Spiller A kan garantere seier, eller B hvis Spiller B kan garantere seier. Little Cyan Fish vil spille som den andre spilleren.

Spill deretter nøyaktig $m$ runder som følger.

• Hvis du spiller som A, skriv ut en linje som inneholder et enkelt heltall $e$ ($1 \le e \le m$), indeksen til en kant som ikke har blitt valgt i noen tidligere runde. Som svar vil du få et enkelt heltall $x$ på en linje. Node $x$ er et endepunkt på kant $e$, og fargen dens endres til den nåværende fargen til det andre endepunktet.
• Hvis du spiller som B, les inn et enkelt heltall $e$ ($1 \le e \le m$) på en linje, indeksen til en kant som ikke har blitt valgt i noen tidligere runde. Skriv ut en linje som inneholder et enkelt heltall $x$, et endepunkt på kant $e$. Fargen til node $x$ endres til den nåværende fargen til det andre endepunktet.

Etter alle $m$ rundene, les inn et enkelt heltall. Dette heltallet er 1 hvis du valgte riktig rolle og vant spillet. Etter å ha mottatt 1, fortsett med neste testtilfelle. Etter det siste testtilfellet skal programmet ditt avsluttes.

Interaktoren vil sende -1 hvis du velger feil rolle, gjør et ugyldig trekk eller taper et spill. Hvis du mottar -1 på noe tidspunkt, skal programmet ditt avsluttes umiddelbart.

Etter at du har skrevet ut rollen din eller et trekk, ikke glem å skrive ut et linjeskifttegn og tømme utdatastrømmen (flush).

Testverktøy: Et testverktøy er tilgjengelig for å hjelpe deltakerne med å utvikle og teste løsningene sine. Du kan laste ned dette verktøyet fra vedleggene. Kjør verktøyet med valget -h for å vise bruksinstruksjoner. Testverktøyet dekker bare noen av testscenariene og funksjonene som støttes av den offisielle interaktoren.

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 to spillene i eksempelet er vist nedenfor. I hvert steg velger A den uthevede kanten, og B farger om den innringede noden. Stiplede kanter ble valgt tidligere.