Ini adalah soal interaktif.

Little Cyan Fish memiliki sebuah graf tak berarah sederhana dengan $n$ verteks yang diberi label dari $1$ hingga $n$ dan $m$ sisi yang diberi label dari $1$ hingga $m$. Pada awalnya, warna verteks $i$ adalah $i$.

Dua pemain, A dan B, memainkan sebuah permainan yang terdiri dari $m$ ronde. Pada setiap ronde, para pemain melakukan tindakan berikut secara berurutan:

• Pemain A memilih sebuah sisi $(u, v)$ yang belum pernah dipilih pada ronde sebelumnya.
• Pemain B memilih salah satu titik ujung dari sisi ini dan mengubah warnanya menjadi warna saat ini dari titik ujung lainnya.

Setelah seluruh $m$ ronde selesai, Pemain B menang jika semua verteks memiliki warna yang sama. Jika tidak, Pemain A menang.

Little Cyan Fish ingin Anda menentukan pemain mana yang dapat menjamin kemenangan terlepas dari langkah pemain lawan. Kemudian bermainlah sebagai pemain tersebut melawan dia dan menangkan permainannya.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi dua bilangan bulat $n$ dan $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$), yang masing-masing menyatakan banyaknya verteks dan banyaknya sisi.

$m$ baris berikutnya mendeskripsikan sisi-sisinya. Baris ke-$i$ dari baris-baris ini berisi dua bilangan bulat $u_i$ dan $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), yang berarti bahwa sisi $i$ menghubungkan verteks $u_i$ dan $v_i$.

Dijamin bahwa graf tidak memiliki gelung (self-loop) maupun sisi ganda (multiple edges). Graf mungkin tidak terhubung.

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $10^5$, dan jumlah $m$ di seluruh kasus uji tidak melebihi $10^5$.

Setelah membaca sebuah graf, selesaikan interaksi untuk kasus uji tersebut sebelum membaca graf berikutnya.

Protokol Interaksi

Untuk memilih peran Anda, keluarkan sebuah baris yang berisi A atau B. Keluarkan A jika Pemain A dapat menjamin kemenangan, atau B jika Pemain B dapat menjamin kemenangan. Little Cyan Fish akan bermain sebagai pemain lainnya.

Kemudian mainkan tepat $m$ ronde sebagai berikut.

• Jika Anda bermain sebagai A, keluarkan sebuah baris yang berisi satu bilangan bulat $e$ ($1 \le e \le m$), yaitu indeks dari sebuah sisi yang belum pernah dipilih pada ronde sebelumnya. Sebagai respons, Anda akan mendapatkan satu bilangan bulat $x$ pada sebuah baris. Verteks $x$ adalah salah satu titik ujung dari sisi $e$, dan warnanya berubah menjadi warna saat ini dari titik ujung lainnya.
• Jika Anda bermain sebagai B, baca satu bilangan bulat $e$ ($1 \le e \le m$) pada sebuah baris, yaitu indeks dari sebuah sisi yang belum pernah dipilih pada ronde sebelumnya. Keluarkan sebuah baris yang berisi satu bilangan bulat $x$, yaitu salah satu titik ujung dari sisi $e$. Warna verteks $x$ berubah menjadi warna saat ini dari titik ujung lainnya.

Setelah seluruh $m$ ronde selesai, baca satu bilangan bulat. Bilangan bulat ini adalah 1 jika Anda memilih peran yang benar dan memenangkan permainan. Setelah menerima 1, lanjutkan ke kasus uji berikutnya. Setelah kasus uji terakhir, program Anda harus berhenti.

Interaktor akan mengirimkan -1 jika Anda memilih peran yang salah, melakukan langkah yang tidak valid, atau kalah dalam permainan. Jika Anda menerima -1 kapan saja, program Anda harus segera berhenti.

Setelah mengeluarkan peran atau langkah Anda, jangan lupa untuk mengeluarkan karakter baris baru (newline) dan melakukan flush pada aliran keluaran.

Alat Penguji: Sebuah alat penguji disediakan untuk membantu peserta mengembangkan dan menguji solusi mereka. Anda dapat mengunduh alat ini dari lampiran. Jalankan alat tersebut dengan opsi -h untuk menampilkan petunjuk penggunaan. Alat penguji ini hanya mencakup sebagian skenario pengujian dan fitur yang didukung oleh interaktor resmi.

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

Dua permainan pada contoh ditunjukkan di bawah ini. Pada setiap langkah, A memilih sisi yang disorot dan B mewarnai ulang verteks yang dilingkari. Sisi bergaris putus-putus telah dipilih sebelumnya.