Ceci est un problème interactif.

Little Cyan Fish possède un graphe non orienté simple comportant $n$ sommets numérotés de $1$ à $n$ et $m$ arêtes numérotées de $1$ à $m$. Initialement, la couleur du sommet $i$ est $i$.

Deux joueurs, A et B, jouent à un jeu composé de $m$ manches. À chaque manche, les joueurs effectuent les actions suivantes dans l'ordre :

• Le joueur A choisit une arête $(u, v)$ qui n'a été choisie lors d'aucune manche précédente.
• Le joueur B choisit l'une des extrémités de cette arête et remplace sa couleur par la couleur actuelle de l'autre extrémité.

Après l'ensemble des $m$ manches, le joueur B gagne si tous les sommets ont la même couleur. Sinon, le joueur A gagne.

Little Cyan Fish souhaite que vous déterminiez quel joueur peut s'assurer la victoire quels que soient les coups de l'autre joueur. Jouez ensuite dans le rôle de ce joueur contre lui et remportez la partie.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T \le 10^4$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient deux entiers $n$ et $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$), indiquant respectivement le nombre de sommets et le nombre d'arêtes.

Les $m$ lignes suivantes décrivent les arêtes. La $i$-ième de ces lignes contient deux entiers $u_i$ et $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), ce qui signifie que l'arête $i$ relie les sommets $u_i$ et $v_i$.

Il est garanti que le graphe ne contient ni boucles ni arêtes multiples. Le graphe peut être non connexe.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $10^5$, et que la somme de $m$ sur tous les cas de test ne dépasse pas $10^5$.

Après avoir lu un graphe, terminez l'interaction pour ce cas de test avant de lire le graphe suivant.

Interaction

Pour choisir votre rôle, affichez une ligne contenant A ou B. Affichez A si le joueur A peut s'assurer la victoire, ou B si le joueur B peut s'assurer la victoire. Little Cyan Fish jouera le rôle de l'autre joueur.

Jouez ensuite exactement $m$ manches comme suit.

• Si vous jouez le rôle de A, affichez une ligne contenant un seul entier $e$ ($1 \le e \le m$), l'indice d'une arête qui n'a été choisie lors d'aucune manche précédente. En réponse, vous recevrez un seul entier $x$ sur une ligne. Le sommet $x$ est une extrémité de l'arête $e$, et sa couleur prend la couleur actuelle de l'autre extrémité.
• Si vous jouez le rôle de B, lisez un seul entier $e$ ($1 \le e \le m$) sur une ligne, l'indice d'une arête qui n'a été choisie lors d'aucune manche précédente. Affichez une ligne contenant un seul entier $x$, une extrémité de l'arête $e$. La couleur du sommet $x$ prend la couleur actuelle de l'autre extrémité.

Après l'ensemble des $m$ manches, lisez un seul entier. Cet entier vaut 1 si vous avez choisi le bon rôle et remporté la partie. Après avoir reçu 1, passez au cas de test suivant. Après le dernier cas de test, votre programme doit se terminer.

L'interacteur enverra -1 si vous choisissez un rôle incorrect, effectuez un coup invalide ou perdez une partie. Si vous recevez -1 à n'importe quel moment, votre programme doit se terminer immédiatement.

Après avoir affiché votre rôle ou un coup, n'oubliez pas d'afficher un caractère de retour à la ligne et de vider le tampon de sortie (flush).

Outil de test : Un outil de test est fourni pour aider les participants à développer et tester leurs solutions. Vous pouvez télécharger cet outil depuis les pièces jointes. Exécutez l'outil avec l'option -h pour afficher les instructions d'utilisation. L'outil de test ne couvre qu'une partie des scénarios de test et des fonctionnalités pris en charge par l'interacteur officiel.

Exemples

Entrée 1

2
3 2
2 3
1 2

1

2

1
4 3
1 2
2 3
3 4


2

4

3
1

Sortie 1

B

3

1






A
1

3

2

Remarque

Les deux parties de l'exemple sont illustrées ci-dessous. À chaque étape, A sélectionne l'arête mise en évidence et B recolore le sommet entouré. Les arêtes en pointillés ont été choisies précédemment.