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