Это интерактивная задача.
Рассмотрим связный неориентированный граф, состоящий из \(n\) вершин и \(m\) ребер. Каждая вершина может быть окрашена в один из трех цветов: \(1\), \(2\) или \(3\). Изначально все вершины не окрашены.
Алиса и Боб играют в игру, состоящую из \(n\) раундов. В каждом раунде происходит следующий двухэтапный процесс:
- Алиса выбирает два различных цвета.
- Боб выбирает непокрашенную вершину и красит ее в один из двух цветов, выбранных Алисой.
Алиса выигрывает, если существует ребро, соединяющее две вершины одного цвета. В противном случае побеждает Боб.
Вам дан граф. Ваша задача — решить, за кого из игроков вы хотите играть, и выиграть игру.
Протокол взаимодействия
Для каждого набора входных данных необходимо вывести одну строку, содержащую либо «Alice», либо «Bob» — игрока, за которого вы хотите играть.
Затем происходит \(n\) раундов, в каждом из которых происходит данный двухэтапный процесс:
- Алиса (либо вы, либо собеседник) выводит два целых числа \(a\) и \(b\) (\(1 \le a, b \le 3\), \(a \neq b\)) — цвета, выбранные Алисой.
- Боб (либо вы, либо собеседник) выводит два целых числа \(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;
- смотрите документацию для других языков.
Взломы в этой задаче отключены.
Примечание
Обратите внимание, что приведенные наборы входных данных являются примерами игр и не обязательно представляют собой оптимальную стратегию для обоих игроков.
В первом наборе входных данных вы решили играть за Алису.
- Алиса выбирает два цвета: \(3\) и \(1\). Боб выбирает вершину \(3\) и окрашивает ее в цвет \(1\).
- Алиса выбирает два цвета: \(1\) и \(2\). Боб выбирает вершину \(2\) и окрашивает ее в цвет \(2\).
- Алиса выбирает два цвета: \(2\) и \(1\). Боб выбирает вершину \(1\) и окрашивает ее в цвет \(1\).
Алиса выигрывает, потому что ребро \((3, 1)\) соединяет две вершины одного цвета.
Во втором наборе входных данных вы решили играть за Боба.
- Алиса выбирает два цвета: \(2\) и \(3\). Боб выбирает вершину \(1\) и окрашивает ее в цвет \(2\).
- Алиса выбирает два цвета: \(1\) и \(2\). Боб выбирает вершину \(2\) и окрашивает ее в цвет \(1\).
- Алиса выбирает два цвета: \(2\) и \(1\). Боб выбирает вершину \(4\) и окрашивает ее в цвет \(1\).
- Алиса выбирает два цвета: \(3\) и \(1\). Боб выбирает вершину \(3\) и окрашивает ее в цвет \(3\).
Боб выигрывает, потому что нет ребер, соединяющих вершины одного цвета.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|