Dies ist ein interaktives Problem.

Little Cyan Fish hat einen einfachen ungerichteten Graphen mit $n$ Knoten, die von $1$ bis $n$ nummeriert sind, und $m$ Kanten, die von $1$ bis $m$ nummeriert sind. Zu Beginn hat der Knoten $i$ die Farbe $i$.

Zwei Spieler, A und B, spielen ein Spiel, das aus $m$ Runden besteht. In jeder Runde führen die Spieler nacheinander die folgenden Aktionen aus:

• Spieler A wählt eine Kante $(u, v)$, die in keiner vorherigen Runde gewählt wurde.
• Spieler B wählt einen Endpunkt dieser Kante und ändert dessen Farbe in die aktuelle Farbe des anderen Endpunkts.

Nach allen $m$ Runden gewinnt Spieler B, wenn alle Knoten dieselbe Farbe haben. Andernfalls gewinnt Spieler A.

Little Cyan Fish möchte, dass du bestimmst, welcher Spieler unabhängig von den Zügen des anderen Spielers einen Sieg garantieren kann. Spiele anschließend als dieser Spieler gegen ihn und gewinne das Spiel.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile zwei ganze Zahlen $n$ und $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$), die die Anzahl der Knoten bzw. die Anzahl der Kanten angeben.

Die nächsten $m$ Zeilen beschreiben die Kanten. Die $i$-te dieser Zeilen enthält zwei ganze Zahlen $u_i$ und $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), was bedeutet, dass die Kante $i$ die Knoten $u_i$ und $v_i$ verbindet.

Es wird garantiert, dass der Graph keine Schleifen oder Mehrfachkanten enthält. Der Graph kann unzusammenhängend sein.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $10^5$ nicht überschreitet und dass die Summe von $m$ über alle Testfälle $10^5$ nicht überschreitet.

Schließe nach dem Einlesen eines Graphen die Interaktion für diesen Testfall ab, bevor du den nächsten Graphen einliest.

Interaktion

Um deine Rolle zu wählen, gib eine Zeile aus, die A oder B enthält. Gib A aus, wenn Spieler A einen Sieg garantieren kann, oder B, wenn Spieler B einen Sieg garantieren kann. Little Cyan Fish wird als der andere Spieler spielen.

Spiele anschließend genau $m$ Runden wie folgt.

• Wenn du als A spielst, gib eine Zeile mit einer einzelnen ganzen Zahl $e$ ($1 \le e \le m$) aus, dem Index einer Kante, die in keiner vorherigen Runde gewählt wurde. Als Antwort erhältst du eine einzelne ganze Zahl $x$ in einer Zeile. Der Knoten $x$ ist ein Endpunkt der Kante $e$, und seine Farbe ändert sich in die aktuelle Farbe des anderen Endpunkts.
• Wenn du als B spielst, lies eine einzelne ganze Zahl $e$ ($1 \le e \le m$) in einer Zeile ein, den Index einer Kante, die in keiner vorherigen Runde gewählt wurde. Gib eine Zeile mit einer einzelnen ganzen Zahl $x$ aus, einem Endpunkt der Kante $e$. Die Farbe des Knotens $x$ ändert sich in die aktuelle Farbe des anderen Endpunkts.

Lies nach allen $m$ Runden eine einzelne ganze Zahl ein. Diese ganze Zahl ist 1, wenn du die richtige Rolle gewählt und das Spiel gewonnen hast. Fahre nach dem Erhalt von 1 mit dem nächsten Testfall fort. Nach dem letzten Testfall muss sich dein Programm beenden.

Der Interaktor sendet -1, wenn du eine falsche Rolle wählst, einen ungültigen Zug machst oder ein Spiel verlierst. Wenn du zu irgendeinem Zeitpunkt -1 erhältst, muss sich dein Programm sofort beenden.

Vergiss nicht, nach der Ausgabe deiner Rolle oder eines Zuges ein Zeilenumbruchzeichen auszugeben und den Ausgabepuffer zu leeren (flush).

Testwerkzeug: Es wird ein Testwerkzeug bereitgestellt, um die Teilnehmer bei der Entwicklung und beim Testen ihrer Lösungen zu unterstützen. Du kannst dieses Werkzeug aus den Anhängen herunterladen. Führe das Werkzeug mit der Option -h aus, um Anweisungen zur Verwendung anzuzeigen. Das Testwerkzeug deckt nur einige der Testszenarien und Funktionen ab, die vom offiziellen Interaktor unterstützt werden.

Beispiele

Eingabe 1

2
3 2
2 3
1 2

1

2

1
4 3
1 2
2 3
3 4


2

4

3
1

Ausgabe 1

B

3

1






A
1

3

2

Hinweis

Die beiden Spiele aus dem Beispiel sind unten dargestellt. In jedem Schritt wählt A die hervorgehobene Kante aus und B färbt den eingekreisten Knoten um. Gestrichelte Kanten wurden bereits zuvor gewählt.