To jest zadanie interaktywne.

Little Cyan Fish ma prosty graf nieskierowany o $n$ wierzchołkach ponumerowanych od $1$ do $n$ oraz $m$ krawędziach ponumerowanych od $1$ do $m$. Początkowo kolor wierzchołka $i$ jest równy $i$.

Dwóch graczy, A oraz B, rozgrywa grę składającą się z $m$ rund. W każdej rundzie gracze wykonują po kolei następujące akcje:

• Gracz A wybiera krawędź $(u, v)$, która nie została wybrana w żadnej poprzedniej rundzie.
• Gracz B wybiera jeden z końców tej krawędzi i zmienia jego kolor na aktualny kolor drugiego końca.

Po wszystkich $m$ rundach gracz B wygrywa, jeśli wszystkie wierzchołki mają ten sam kolor. W przeciwnym razie wygrywa gracz A.

Little Cyan Fish chce, abyś ustalił, który gracz może zagwarantować sobie zwycięstwo niezależnie od ruchów drugiego gracza. Następnie zagraj jako ten gracz przeciwko niemu i wygraj grę.

Wejście

Zadanie zawiera wiele przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$), oznaczające odpowiednio liczbę wierzchołków oraz liczbę krawędzi.

Kolejne $m$ wierszy opisuje krawędzie. $i$-ty z tych wierszy zawiera dwie liczby całkowite $u_i$ oraz $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), co oznacza, że krawędź $i$ łączy wierzchołki $u_i$ oraz $v_i$.

Gwarantowane jest, że graf nie zawiera pętli własnych ani krawędzi wielokrotnych. Graf może być niespójny.

Gwarantowane jest, że suma wartości $n$ po wszystkich przypadkach testowych nie przekracza $10^5$, oraz że suma wartości $m$ po wszystkich przypadkach testowych nie przekracza $10^5$.

Po wczytaniu grafu dokończ interakcję dla tego przypadku testowego przed wczytaniem kolejnego grafu.

Interakcja

Aby wybrać swoją rolę, wypisz wiersz zawierający A lub B. Wypisz A, jeśli gracz A może zagwarantować sobie zwycięstwo, lub B, jeśli gracz B może zagwarantować sobie zwycięstwo. Little Cyan Fish zagra jako drugi gracz.

Następnie rozegraj dokładnie $m$ rund w następujący sposób.

• Jeśli grasz jako A, wypisz wiersz zawierający jedną liczbę całkowitą $e$ ($1 \le e \le m$) — numer krawędzi, która nie została wybrana w żadnej poprzedniej rundzie. W odpowiedzi otrzymasz w wierszu jedną liczbę całkowitą $x$. Wierzchołek $x$ jest końcem krawędzi $e$, a jego kolor zmienia się na aktualny kolor drugiego końca.
• Jeśli grasz jako B, wczytaj z wiersza jedną liczbę całkowitą $e$ ($1 \le e \le m$) — numer krawędzi, która nie została wybrana w żadnej poprzedniej rundzie. Wypisz wiersz zawierający jedną liczbę całkowitą $x$ — koniec krawędzi $e$. Kolor wierzchołka $x$ zmienia się na aktualny kolor drugiego końca.

Po wszystkich $m$ rundach wczytaj jedną liczbę całkowitą. Liczba ta jest równa 1, jeśli wybrałeś właściwą rolę i wygrałeś grę. Po otrzymaniu 1 przejdź do kolejnego przypadku testowego. Po ostatnim przypadku testowym Twój program powinien zakończyć działanie.

Interaktor wyśle -1, jeśli wybierzesz nieprawidłową rolę, wykonasz nieprawidłowy ruch lub przegrasz grę. Jeśli w dowolnym momencie otrzymasz -1, Twój program powinien natychmiast zakończyć działanie.

Po wypisaniu swojej roli lub ruchu nie zapomnij wypisać znaku nowej linii i opróżnić bufora wyjścia (flush).

Narzędzie testujące: Udostępniono narzędzie testujące, aby pomóc zawodnikom w tworzeniu i testowaniu swoich rozwiązań. Narzędzie to można pobrać z załączników. Uruchom narzędzie z opcją -h, aby wyświetlić instrukcję użycia. Narzędzie testujące obejmuje tylko niektóre scenariusze testowe i funkcje obsługiwane przez oficjalny interaktor.

Przykład

Wejście 1

2
3 2
2 3
1 2

1

2

1
4 3
1 2
2 3
3 4


2

4

3
1

Wyjście 1

B

3

1






A
1

3

2

Uwagi

Dwie rozgrywki z przykładu przedstawiono poniżej. W każdym kroku A wybiera wyróżnioną krawędź, a B przemalowuje zakreślony wierzchołek. Krawędzie przerywane zostały wybrane wcześniej.