불을 켜고, 문을 닫아라!

이 문제는 인터랙티브 문제입니다.

N시에서 새로 인기를 얻고 있는 퀘스트에서 플레이어는 방 개수를 알 수 없는 미로에서 빠져나와야 합니다. 각 방에는 문이 여러 개 있고, 전구가 하나, 스위치가 두 개 있습니다. 방마다 첫 번째 스위치로 전구를 켜고 끌 수 있으며, 이 스위치는 원하는 만큼 몇 번이든 사용할 수 있습니다. 두 번째 스위치는 한 번만 작동시킬 수 있습니다. 이 스위치는 플레이어가 방의 문 중 하나를 통과한 직후 그 방에서 나가는 모든 문을 잠그고, 이후 그 방은 접근할 수 없게 됩니다.

처음에는 모든 방의 문이 열려 있으며, 일부 방에는 불이 켜져 있습니다. 목표는 모든 방의 전구를 켜고, 아무 방이나 하나를 제외한 나머지 모든 방을 잠그는 것입니다. 방에 표시를 남길 수 있다면 문제가 간단하겠지만, 퀘스트 규칙상 이는 금지되어 있습니다. 플레이어가 방에 들어가면 그 방의 문 개수, 불이 켜져 있는지 여부, 방금 들어온 문만 볼 수 있습니다. 방에 들어갈 때마다 문은 항상 같은 순서로 보이며, 같은 방식으로 번호가 매겨집니다.

플레이어는 다음 행동을 할 수 있습니다:

• 현재 있는 방의 전구를 켭니다.
• 현재 있는 방의 전구를 끕니다.
• 문 중 하나를 통과하려고 시도합니다. 건너편 방이 잠겨 있지 않으면 성공합니다. 문을 통과하면서 떠나는 방을 잠그는 스위치를 작동시킬 수도 있습니다.
• 현재 방을 제외한 모든 방이 잠겨 있고 모든 방의 불이 켜져 있다고 판단되면 게임을 끝낼 수 있습니다.

프로그램은 처음에 시작 방의 불이 켜져 있는지 여부, 그 방의 문 개수, 그리고 0을 입력받습니다. 플레이어는 어떤 문으로도 이 방에 들어오지 않았으므로 마지막 값은 0입니다.

방은 최대 50개, 문은 최대 100개입니다. 각 문은 두 방을 연결하며 한 번만 셉니다. 모든 방에서 문을 따라 다른 모든 방으로 갈 수 있음이 보장됩니다. 또한 두 방을 잇는 문은 최대 하나입니다.

샘플 테스트의 형식은 첫 줄에 방 개수와 문 개수, 다음으로 각 방의 초기 전구 상태(켜짐 1, 꺼짐 0), 이어서 문으로 연결된 방의 쌍들, 마지막으로 시작 방 번호가 주어지는 순서입니다. 첫 세 테스트는 이 구조를 보여 주지만, 프로그램이 실제로 받는 입력과는 맞지 않습니다. 가능한 상호작용 예시는 힌트 아래에 있습니다.

프로그램이 보내는 질의는 $30\,000$개를 넘을 수 없습니다. 이 제한을 넘으면 Wrong Answer 판정을 받습니다. 게임 종료도 질의 한 번으로 셉니다.

모든 질의 후에는 출력 버퍼를 비워야 합니다(flush). C++에서는 fflush(stdout), Java에서는 System.out.flush(), Python에서는 stdout.flush(), Pascal에서는 flush(output)을 사용합니다. 그 밖의 언어는 해당 언어의 문서를 참고합니다.

그래프가 트리라는 주석은 같은 방을 두 번 방문하지 않는 길이 2보다 긴 순환 경로가 미로에 하나도 없다는 뜻입니다.

그래프가 사이클이라는 주석은 모든 방이 같은 순환 경로 위에 있고, 이 경로가 어떤 방도 두 번 방문하지 않는다는 뜻입니다.

아래는 첫 번째 테스트에서 가능한 상호작용 프로토콜 예시입니다. 왼쪽 열은 검사 프로그램의 출력이고, 오른쪽 열은 참가자 프로그램이 출력할 수 있는 내용입니다.

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