게르쿨레스

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

오스탑은 반쯤 책임감이 있고 반쯤 유령 같은 동료 스쿰브리예비치를 게르쿨레스의 복도에서 쫓고 있습니다. 건물은 여러 방으로 이루어져 있고, 방들은 양방향 복도로 연결되어 있습니다. 어떤 방에서든 다른 방으로 가는 길은 정확히 한 가지이며, 그 과정에서 다른 방들을 거칠 수 있습니다. 스쿰브리예비치는 이 방들 중 한 곳에 있으며, 움직이지 않습니다.

새로운 방에 들어설 때마다 그는 어느 복도로 들어왔는지 기억하지 못합니다. 다만 그 방과 이웃 방을 잇는 복도에는 1부터 그 방에 있는 복도 수까지 번호가 붙어 있다는 것은 압니다. 오스탑은 각 방의 복도 번호가 시간이 지나도 바뀌지 않는다는 것을 압니다. 추격은 다음과 같이 진행됩니다.

• 오스탑은 다른 방으로 갈 복도의 번호를 고릅니다.
• 선택한 복도로 다른 방에 들어갑니다.
• 새 방에서도 그 방의 복도 수만 알 수 있습니다.
• 내면의 목소리가 스쿰브리예비치에게 가까워졌는지 멀어졌는지 알려 줍니다.
• 경우에 따라 오스탑이 마침내 스쿰브리예비치를 만나면 추격이 끝납니다.

오스탑이 잡기 어려운 스쿰브리예비치를 잡도록 도와주세요.

프로그램이 올바르게 동작하려면 출력할 때마다 반드시 버퍼를 비워야 합니다.

• Pascal: flush(output);
• C/C++: fflush(stdout);
• Java: System.out.flush();
• Python: sys.stdout.flush();

또한 출력하는 줄의 끝마다 줄바꿈을 넣어야 합니다.