Questo è un problema interattivo.

Little Cyan Fish ha un grafo semplice non orientato con $n$ vertici numerati da $1$ a $n$ e $m$ archi numerati da $1$ a $m$. Inizialmente, il colore del vertice $i$ è $i$.

Due giocatori, A e B, giocano una partita composta da $m$ turni. In ogni turno, i giocatori compiono le seguenti azioni in ordine:

• Il giocatore A sceglie un arco $(u, v)$ che non è stato scelto in nessun turno precedente.
• Il giocatore B sceglie uno degli estremi di questo arco e cambia il suo colore con il colore attuale dell'altro estremo.

Dopo tutti gli $m$ turni, il giocatore B vince se tutti i vertici hanno lo stesso colore. Altrimenti, vince il giocatore A.

Little Cyan Fish vuole che tu determini quale giocatore può garantirsi la vittoria indipendentemente dalle mosse dell'altro giocatore. Poi gioca nei panni di quel giocatore contro di lui e vinci la partita.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T \le 10^4$), che indica il numero di casi di test.

Per ogni caso di test, la prima riga contiene due interi $n$ e $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$), che indicano rispettivamente il numero di vertici e il numero di archi.

Le successive $m$ righe descrivono gli archi. La $i$-esima di queste righe contiene due interi $u_i$ e $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), il che significa che l'arco $i$ collega i vertici $u_i$ e $v_i$.

È garantito che il grafo non abbia cappi o archi multipli. Il grafo può essere disconnesso.

È garantito che la somma di $n$ su tutti i casi di test non superi $10^5$, e che la somma di $m$ su tutti i casi di test non superi $10^5$.

Dopo aver letto un grafo, completa l'interazione per quel caso di test prima di leggere il grafo successivo.

Interazione

Per scegliere il tuo ruolo, stampa una riga contenente A oppure B. Stampa A se il giocatore A può garantirsi la vittoria, oppure B se il giocatore B può garantirsi la vittoria. Little Cyan Fish giocherà nei panni dell'altro giocatore.

Poi gioca esattamente $m$ turni come segue.

• Se giochi come A, stampa una riga contenente un singolo intero $e$ ($1 \le e \le m$), l'indice di un arco che non è stato scelto in nessun turno precedente. Come risposta, riceverai un singolo intero $x$ su una riga. Il vertice $x$ è un estremo dell'arco $e$, e il suo colore cambia con il colore attuale dell'altro estremo.
• Se giochi come B, leggi un singolo intero $e$ ($1 \le e \le m$) su una riga, l'indice di un arco che non è stato scelto in nessun turno precedente. Stampa una riga contenente un singolo intero $x$, un estremo dell'arco $e$. Il colore del vertice $x$ cambia con il colore attuale dell'altro estremo.

Dopo tutti gli $m$ turni, leggi un singolo intero. Questo intero è 1 se hai scelto il ruolo corretto e hai vinto la partita. Dopo aver ricevuto 1, continua con il caso di test successivo. Dopo l'ultimo caso di test, il tuo programma deve terminare.

L'interattore invierà -1 se scegli un ruolo errato, effettui una mossa non valida o perdi una partita. Se ricevi -1 in qualsiasi momento, il tuo programma deve terminare immediatamente.

Dopo aver stampato il tuo ruolo o una mossa, non dimenticare di stampare un carattere di ritorno a capo e di svuotare il buffer di output (flush).

Strumento di test: È fornito uno strumento di test per aiutare i concorrenti a sviluppare e testare le proprie soluzioni. Puoi scaricare questo strumento dagli allegati. Esegui lo strumento con l'opzione -h per visualizzare le istruzioni per l'uso. Lo strumento di test copre solo alcuni degli scenari di test e delle funzionalità supportate dall'interattore ufficiale.

Esempi

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

Nota

Le due partite dell'esempio sono mostrate qui sotto. In ogni passo, A seleziona l'arco evidenziato e B ricolora il vertice cerchiato. Gli archi tratteggiati sono stati scelti in precedenza.