G. Включи свет, закрой двери!
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

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

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

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

В секции «Примеры» приведены некоторые варианты возможных конфигураций лабиринта. Первая строка содержит количество комнат и количество дверей в лабиринте, затем идёт описание начального состояния лампочки в комнате (1 если лампочка горит, и 0, если не горит), далее следуют пары комнат, соединённых дверьми, а в конце содержится одно число — номер стартовой комнаты. Обратите внимание, данное описание показывает структуру первых трёх тестов, но не соответствует тому, что ваша программа получит на вход. Пример возможного взаимодействия вашей и проверяющей программ приведён в разделе «Замечание».

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

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

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

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

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

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

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

  • «turn on» — включить свет в текущей комнате. Если свет уже включен, то ничего не происходит. Проверяющая программа никак не отвечает на данный запрос.
  • «turn off» — выключить свет в текущей комнате. Если свет уже выключен, то ничего не происходит. Проверяющая программа никак не отвечает на данный запрос.
  • «go edgeId keep|lock» — пойти в дверь номер edgeId, считая что двери нумеруются начиная с 1. При этом параметр keep означает, что комната остается открытой, а lock означает, что после выхода из комнаты она закроется и больше не будет доступна. Ответом проверяющей программы будет:
    • locked, если комната, в которую ведёт данная дверь, закрыта. В этом случае игрок остаётся в данной комнате а действие lock (если оно было указано) не выполняется.
    • строка on|off edgeCount edgeId, если игрок успешно перейдёт в другую комнату. Слово on означает, что свет в текущей комнате включен, а слово off — что выключен. edgeCount равняется количеству дверей в данной комнате, а edgeId — номеру двери, через которую игрок только что пришёл.
  • «done» — завершить игру. Данный запрос выполняется в конце, когда игрок считает, что уже включил свет во всех комнатах и запер все комнаты, кроме той в которой сейчас находится. Обратите внимание, что игрок может закончить игру в любой комнате. Если в какой-то комнате свет будет выключен или какая-то комната кроме данной будет не заперта, то решение получит вердикт Wrong Answer. После выполнения данного запроса программа должна немедленно завершить работу.

Если Ваша программа выведет какую-то другую команду или попытается перейти по двери с номером, которого не существует, то она получит вердит Presentation error.

Примеры
Входные данные
2 1
0 0
1 2
1
Выходные данные
7
Входные данные
3 2
1 1 1
1 2
2 3
2
Выходные данные
17
Входные данные
3 3
0 1 1
1 2
2 3
3 1
1
Выходные данные
43
Примечание

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

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

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


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