Este es un problema interactivo.

Little Cyan Fish tiene un grafo simple no dirigido con $n$ vértices numerados de $1$ a $n$ y $m$ aristas numeradas de $1$ a $m$. Inicialmente, el color del vértice $i$ es $i$.

Dos jugadores, A y B, juegan una partida que consta de $m$ rondas. En cada ronda, los jugadores realizan las siguientes acciones en orden:

• El jugador A elige una arista $(u, v)$ que no haya sido elegida en ninguna ronda anterior.
• El jugador B elige uno de los extremos de esta arista y cambia su color al color actual del otro extremo.

Después de las $m$ rondas, el jugador B gana si todos los vértices tienen el mismo color. De lo contrario, gana el jugador A.

Little Cyan Fish quiere que determines qué jugador puede garantizar la victoria independientemente de los movimientos del otro jugador. Luego juega como ese jugador contra él y gana la partida.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un solo entero $T$ ($1 \le T \le 10^4$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene dos enteros $n$ y $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$), que indican el número de vértices y el número de aristas, respectivamente.

Las siguientes $m$ líneas describen las aristas. La $i$-ésima de estas líneas contiene dos enteros $u_i$ y $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), lo que significa que la arista $i$ conecta los vértices $u_i$ y $v_i$.

Se garantiza que el grafo no tiene bucles ni aristas múltiples. El grafo puede ser desconexo.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $10^5$, y que la suma de $m$ en todos los casos de prueba no supera $10^5$.

Después de leer un grafo, completa la interacción para ese caso de prueba antes de leer el siguiente grafo.

Interacción

Para elegir tu rol, imprime una línea que contenga A o B. Imprime A si el jugador A puede garantizar la victoria, o B si el jugador B puede garantizar la victoria. Little Cyan Fish jugará como el otro jugador.

Luego juega exactamente $m$ rondas de la siguiente manera.

• Si juegas como A, imprime una línea que contenga un solo entero $e$ ($1 \le e \le m$), el índice de una arista que no haya sido elegida en ninguna ronda anterior. Como respuesta, recibirás un solo entero $x$ en una línea. El vértice $x$ es un extremo de la arista $e$, y su color cambia al color actual del otro extremo.
• Si juegas como B, lee un solo entero $e$ ($1 \le e \le m$) en una línea, el índice de una arista que no haya sido elegida en ninguna ronda anterior. Imprime una línea que contenga un solo entero $x$, un extremo de la arista $e$. El color del vértice $x$ cambia al color actual del otro extremo.

Después de las $m$ rondas, lee un solo entero. Este entero es 1 si elegiste el rol correcto y ganaste la partida. Después de recibir 1, continúa con el siguiente caso de prueba. Después del último caso de prueba, tu programa debe terminar.

El interactor enviará -1 si eliges un rol incorrecto, realizas un movimiento inválido o pierdes una partida. Si recibes -1 en cualquier momento, tu programa debe terminar inmediatamente.

Después de imprimir tu rol o un movimiento, no olvides imprimir un carácter de salto de línea y vaciar el búfer de salida (flush).

Herramienta de prueba: Se proporciona una herramienta de prueba para ayudar a los concursantes a desarrollar y probar sus soluciones. Puedes descargar esta herramienta desde los archivos adjuntos. Ejecuta la herramienta con la opción -h para mostrar las instrucciones de uso. La herramienta de prueba cubre solo algunos de los escenarios de prueba y características compatibles con el interactor oficial.

Ejemplos

Entrada 1

2
3 2
2 3
1 2

1

2

1
4 3
1 2
2 3
3 4


2

4

3
1

Salida 1

B

3

1






A
1

3

2

Nota

Las dos partidas del ejemplo se muestran a continuación. En cada paso, A selecciona la arista resaltada y B vuelve a colorear el vértice rodeado por un círculo. Las aristas discontinuas fueron elegidas anteriormente.