E. Игра с раскрасками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Рассмотрим связный неориентированный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер. Каждая вершина может быть окрашена в один из трех цветов: $$$1$$$, $$$2$$$ или $$$3$$$. Изначально все вершины не окрашены.

Алиса и Боб играют в игру, состоящую из $$$n$$$ раундов. В каждом раунде происходит следующий двухэтапный процесс:

  1. Алиса выбирает два различных цвета.
  2. Боб выбирает непокрашенную вершину и красит ее в один из двух цветов, выбранных Алисой.

Алиса выигрывает, если существует ребро, соединяющее две вершины одного цвета. В противном случае побеждает Боб.

Вам дан граф. Ваша задача — решить, за кого из игроков вы хотите играть, и выиграть игру.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$m$$$ ($$$1 \le n \le 10^4$$$, $$$n - 1 \le m \le \min(\frac{n \cdot (n - 1)}{2}, 10^4)$$$) — количество вершин и количество ребер в графе соответственно.

Каждая из следующих $$$m$$$ строк каждого набора входных данных содержит по два целых числа $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — ребра графа. Гарантируется, что граф связен, и что в нем нет петель и кратных ребер.

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

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

Для каждого набора входных данных необходимо вывести одну строку, содержащую либо «Alice», либо «Bob» — игрока, за которого вы хотите играть.

Затем происходит $$$n$$$ раундов, в каждом из которых происходит данный двухэтапный процесс:

  1. Алиса (либо вы, либо собеседник) выводит два целых числа $$$a$$$ и $$$b$$$ ($$$1 \le a, b \le 3$$$, $$$a \neq b$$$) — цвета, выбранные Алисой.
  2. Боб (либо вы, либо собеседник) выводит два целых числа $$$i$$$ и $$$c$$$ ($$$1 \le i \le n$$$, $$$c = a$$$ или $$$c = b$$$) — вершина и цвет, выбранные Бобом. Вершина $$$i$$$ должна быть неокрашенной.

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

В конце $$$n$$$ раундов, если ваше решение проиграло, жюри выведет «-1» и вы получите вердикт Неправильный ответ.

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

Обратите внимание, что если вы играете за Алису, и уже есть ребро, соединяющее вершины одного цвета, интерактор не завершит игру досрочно, и будут сыграны все $$$n$$$ раундов.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Взломы в этой задаче отключены.

Пример
Входные данные
2
3 3
1 2
2 3
3 1


3 1

2 2

1 1
4 4
1 2
2 3
3 4
4 1

2 3

1 2

2 1

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





Alice
3 1

1 2

2 1






Bob

1 2

2 1

4 1

3 3
Примечание

Обратите внимание, что приведенные наборы входных данных являются примерами игр и не обязательно представляют собой оптимальную стратегию для обоих игроков.

В первом наборе входных данных вы решили играть за Алису.

  1. Алиса выбирает два цвета: $$$3$$$ и $$$1$$$. Боб выбирает вершину $$$3$$$ и окрашивает ее в цвет $$$1$$$.
  2. Алиса выбирает два цвета: $$$1$$$ и $$$2$$$. Боб выбирает вершину $$$2$$$ и окрашивает ее в цвет $$$2$$$.
  3. Алиса выбирает два цвета: $$$2$$$ и $$$1$$$. Боб выбирает вершину $$$1$$$ и окрашивает ее в цвет $$$1$$$.

Алиса выигрывает, потому что ребро $$$(3, 1)$$$ соединяет две вершины одного цвета.

Во втором наборе входных данных вы решили играть за Боба.

  1. Алиса выбирает два цвета: $$$2$$$ и $$$3$$$. Боб выбирает вершину $$$1$$$ и окрашивает ее в цвет $$$2$$$.
  2. Алиса выбирает два цвета: $$$1$$$ и $$$2$$$. Боб выбирает вершину $$$2$$$ и окрашивает ее в цвет $$$1$$$.
  3. Алиса выбирает два цвета: $$$2$$$ и $$$1$$$. Боб выбирает вершину $$$4$$$ и окрашивает ее в цвет $$$1$$$.
  4. Алиса выбирает два цвета: $$$3$$$ и $$$1$$$. Боб выбирает вершину $$$3$$$ и окрашивает ее в цвет $$$3$$$.

Боб выигрывает, потому что нет ребер, соединяющих вершины одного цвета.