Это интерактивная задача.

У Маленькой Циановой Рыбки (Little Cyan Fish) есть простой неориентированный граф с $n$ вершинами, пронумерованными от $1$ до $n$, и $m$ рёбрами, пронумерованными от $1$ до $m$. Изначально цвет вершины $i$ равен $i$.

Два игрока, A и B, играют в игру, состоящую из $m$ раундов. В каждом раунде игроки по очереди выполняют следующие действия:

• Игрок A выбирает ребро $(u, v)$, которое не выбиралось ни в одном из предыдущих раундов.
• Игрок B выбирает один из концов этого ребра и меняет его цвет на текущий цвет другого конца.

После всех $m$ раундов игрок B побеждает, если все вершины имеют одинаковый цвет. В противном случае побеждает игрок A.

Маленькая Циановая Рыбка хочет, чтобы вы определили, какой игрок может гарантировать себе победу независимо от ходов другого игрока. Затем сыграйте за этого игрока против него и выиграйте игру.

Входные данные

Входные данные состоят из нескольких наборов входных данных. Первая строка входных данных содержит одно целое число $T$ ($1 \le T \le 10^4$), обозначающее количество наборов входных данных.

Для каждого набора входных данных первая строка содержит два целых числа $n$ и $m$ ($2 \le n \le 10^5$, $1 \le m \le 10^5$), обозначающих количество вершин и количество рёбер соответственно.

Следующие $m$ строк описывают рёбра. $i$-я из этих строк содержит два целых числа $u_i$ и $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), означающих, что ребро $i$ соединяет вершины $u_i$ и $v_i$.

Гарантируется, что в графе нет петель и кратных рёбер. Граф может быть несвязным.

Гарантируется, что сумма $n$ по всем наборам входных данных не превышает $10^5$, а сумма $m$ по всем наборам входных данных не превышает $10^5$.

После считывания графа завершите взаимодействие для этого набора входных данных, прежде чем считывать следующий граф.

Протокол взаимодействия

Чтобы выбрать свою роль, выведите строку, содержащую A или B. Выведите A, если игрок A может гарантировать себе победу, или B, если игрок B может гарантировать себе победу. Маленькая Циановая Рыбка будет играть за другого игрока.

Затем сыграйте ровно $m$ раундов следующим образом.

• Если вы играете за A, выведите строку, содержащую одно целое число $e$ ($1 \le e \le m$) — номер ребра, которое не выбиралось ни в одном из предыдущих раундов. В ответ вы получите одно целое число $x$ в отдельной строке. Вершина $x$ является концом ребра $e$, и её цвет меняется на текущий цвет другого конца.
• Если вы играете за B, считайте одно целое число $e$ ($1 \le e \le m$) в отдельной строке — номер ребра, которое не выбиралось ни в одном из предыдущих раундов. Выведите строку, содержащую одно целое число $x$ — конец ребра $e$. Цвет вершины $x$ меняется на текущий цвет другого конца.

После всех $m$ раундов считайте одно целое число. Это число равно 1, если вы выбрали правильную роль и выиграли игру. После получения 1 переходите к следующему набору входных данных. После последнего набора входных данных ваша программа должна завершиться.

Интерактор отправит -1, если вы выберете неправильную роль, сделаете некорректный ход или проиграете игру. Если вы получите -1 в любой момент, ваша программа должна немедленно завершиться.

После вывода вашей роли или хода не забудьте вывести символ перевода строки и сбросить буфер вывода (flush).

Инструмент для тестирования: Для помощи участникам в разработке и тестировании своих решений предоставляется инструмент для тестирования. Вы можете скачать этот инструмент из вложений. Запустите инструмент с опцией -h, чтобы отобразить инструкции по использованию. Инструмент для тестирования охватывает лишь некоторые из тестовых сценариев и функций, поддерживаемых официальным интерактором.

Примеры

Входные данные 1

2
3 2
2 3
1 2

1

2

1
4 3
1 2
2 3
3 4


2

4

3
1

Выходные данные 1

B

3

1






A
1

3

2

Примечание

Две игры из примера показаны ниже. На каждом шаге A выбирает выделенное ребро, а B перекрашивает обведённую кружком вершину. Пунктирные рёбра были выбраны ранее.