Tämä on vuorovaikutteinen tehtävä.

Little Cyan Fishillä on yksinkertainen suuntaamaton verkko, jossa on $n$ solmua numeroituna $1$:stä $n$:ään ja $m$ kaarta numeroituna $1$:stä $m$:ään. Aluksi solmun $i$ väri on $i$.

Kaksi pelaajaa, A ja B, pelaavat pelin, joka koostuu $m$ kierroksesta. Jokaisella kierroksella pelaajat tekevät seuraavat toiminnot järjestyksessä:

• Pelaaja A valitsee kaaren $(u, v)$, jota ei ole valittu millään aiemmalla kierroksella.
• Pelaaja B valitsee tämän kaaren toisen päätesolmun ja muuttaa sen värin toisen päätesolmun nykyiseksi väriksi.

Kaikkien $m$ kierroksen jälkeen Pelaaja B voittaa, jos kaikilla solmuilla on sama väri. Muussa tapauksessa Pelaaja A voittaa.

Little Cyan Fish haluaa sinun selvittävän, kumpi pelaaja voi varmistaa voiton vastustajan siirroista riippumatta. Pelaa sitten kyseisenä pelaajana häntä vastaan ja voita peli.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T \le 10^4$), joka ilmoittaa testitapausten lukumäärän.

Jokaisessa testitapauksessa ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$), jotka ilmoittavat solmujen lukumäärän ja kaarien lukumäärän.

Seuraavat $m$ riviä kuvaavat kaaret. Näistä riveistä $i$:s sisältää kaksi kokonaislukua $u_i$ ja $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), mikä tarkoittaa, että kaari $i$ yhdistää solmut $u_i$ ja $v_i$.

On taattu, että verkossa ei ole silmukoita eikä moninkertaisia kaaria. Verkko ei välttämättä ole yhtenäinen.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten on enintään $10^5$, ja lukujen $m$ summa yli kaikkien testitapausten on enintään $10^5$.

Kun olet lukenut verkon, suorita kyseisen testitapauksen vuorovaikutus loppuun ennen seuraavan verkon lukemista.

Vuorovaikutusprotokolla

Valitaksesi roolisi tulosta rivi, joka sisältää merkin A tai B. Tulosta A, jos Pelaaja A voi varmistaa voiton, tai B, jos Pelaaja B voi varmistaa voiton. Little Cyan Fish pelaa toisena pelaajana.

Pelaa sitten täsmälleen $m$ kierrosta seuraavasti.

• Jos pelaat pelaajana A, tulosta rivi, joka sisältää yhden kokonaisluvun $e$ ($1 \le e \le m$), joka on jonkin sellaisen kaaren indeksi, jota ei ole valittu millään aiemmalla kierroksella. Vastauksena saat yhden kokonaisluvun $x$ omalla rivillään. Solmu $x$ on kaaren $e$ päätesolmu, ja sen väri muuttuu toisen päätesolmun nykyiseksi väriksi.
• Jos pelaat pelaajana B, lue yhdeltä riviltä yksi kokonaisluku $e$ ($1 \le e \le m$), joka on jonkin sellaisen kaaren indeksi, jota ei ole valittu millään aiemmalla kierroksella. Tulosta rivi, joka sisältää yhden kokonaisluvun $x$, joka on kaaren $e$ päätesolmu. Solmun $x$ väri muuttuu toisen päätesolmun nykyiseksi väriksi.

Kaikkien $m$ kierroksen jälkeen lue yksi kokonaisluku. Tämä kokonaisluku on 1, jos valitsit oikean roolin ja voitit pelin. Saatuasi luvun 1 jatka seuraavaan testitapaukseen. Viimeisen testitapauksen jälkeen ohjelmasi tulee päättyä.

Interaktori lähettää luvun -1, jos valitset väärän roolin, teet virheellisen siirron tai häviät pelin. Jos saat luvun -1 missä tahansa vaiheessa, ohjelmasi tulee päättyä välittömästi.

Roolin tai siirron tulostamisen jälkeen älä unohda tulostaa rivinvaihtomerkkiä ja tyhjentää tulostuspuskuria (flush).

Testaustyökalu: Kilpailijoiden avuksi ratkaisujen kehittämiseen ja testaamiseen tarjotaan testaustyökalu. Voit ladata tämän työkalun liitteistä. Suorita työkalu valitsimella -h nähdäksesi käyttöohjeet. Testaustyökalu kattaa vain osan virallisen interaktorin tukemista testiskenaarioista ja ominaisuuksista.

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

Esimerkin kaksi peliä on esitetty alla. Jokaisessa vaiheessa A valitsee korostetun kaaren ja B värittää ympyröidyn solmun uudelleen. Katkoviivalla merkityt kaaret on valittu aiemmin.