Включи свет, закрой двери!

문제

Это интерактивная задача. В секции <<Протокол взаимодействия>> вы найдёте информацию о том, как сбрасывать буфер вывода (делать операцию 'flush').

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

Изначально все комнаты открыты, и в некоторых из них горит свет. Целью игры является включить свет во всех комнатах лабиринта, а также закрыть все комнаты, кроме одной (любой). Данная задача была бы простой, если бы у игрока была возможность оставлять в комнатах какие-то отметки, но это запрещено правилами квеста. Когда игрок заходит в какую-либо комнату, он видит только количество дверей в этой комнате, горит или не горит в ней свет, а также знает через какую дверь он только что вошёл. Заходя в комнату, игрок всегда видит двери в одном и том же порядке и нумерует из одинаково.

Игрок может выполнять следующие действия:

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

입력

Изначально программе на ввод подаётся информация о том включен ли свет в стартовой комнате, сколько в этой комнате дверей и число $00$ (поскольку игрок не пришёл в эту комнату через какую-то из дверей).

Гарантируется, что число комнат не превосходит $5050$, а число дверей не превосходит $100100$ (каждая дверь соединяет две комнаты и считается один раз). Также гарантируется, что из любой комнаты можно дойти до любой другой, двигаясь только с использованием имеющихся дверей, и что никакая пара комнат не соединена более чем одной дверью.

В секции <<Примеры>> приведены некоторые варианты возможных конфигураций лабиринта. Первая строка содержит количество комнат и количество дверей в лабиринте, затем идёт описание начального состояния лампочки в комнате ($11$ если лампочка горит, и $00$, если не горит), далее следуют пары комнат, соединённых дверьми, а в конце содержится одно число --- номер стартовой комнаты. Обратите внимание, данное описание показывает структуру первых трёх тестов, но не соответствует тому, что ваша программа получит на вход. Пример возможного взаимодействия вашей и проверяющей программ приведён в разделе <<Замечание>>.

출력

Число запросов, сделанных вашей программой, не должно превосходить $3000030\backslash ,000$. При нарушении этого ограничения вы получите вердикт Wrong Answer (неправильный ответ). Завершение игры также считается одним запросом.

После выполнения каждого запроса необходимо сбрасывать буфер вывода (делать операцию 'flush'), для этого можно использовать:

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

В секции <<Примеры>> в графе выходные данные приведено число запросов, использованных некоторым из решений жюри. Данное число следует игнорировать.

힌트

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

Комментарий о том, что граф является циклом, означает что все комнаты лежат на одном циклическом маршруте, не посещающем никакую комнату дважды.

Ниже приведён пример возможного протокола взаимодействия на первом тестовом примере. Левый столбец соответствует выводу проверяющей программы, а правый --- возможному выводу программы участника.

off 1 0
              turn on
              go 1 keep
off 1 1
              turn off
              turn on
              turn on
              go 1 lock
on 1 1
              go 1 lock
locked
              turn off
              turn on
              done