외계인 경비

당신은 극비 정부 연구 시설의 보안 책임자다. 정부가 살아 있는 외계 생명체(ET)를 포획했고, 동료 연구자들을 초청하는 공개 행사를 연다. 모든 손님을 신뢰할 수는 없으므로 각자에게 서로 다른 보안 등급을 부여한다. 등급 5를 받은 손님만 ET가 있는 방에 들어갈 수 있고, 나머지 손님은 시설의 다른 공간을 자유롭게 다닐 수 있다.

방들은 일방통행 에어록으로 연결되어 있어, 각 문은 한 방향으로만 지날 수 있다. 모든 손님은 0번 방으로 입장한다.

ET를 보호하기 위해 ET가 있는 방으로 향하는 경로 위의 정확히 한 방에 무장 경비를 배치한다. 단, 경비는 ET가 있는 방에 들어갈 등급이 없으므로 그 방 자체에는 배치할 수 없다. 경비는 자신이 있는 방을 지나는 모든 손님의 신원과 보안 등급을 검사하므로, ET를 방문할 의도가 없는 손님을 가장 적게 방해하도록 배치하고 싶다. 따라서 경비를 배치할 방은 다음 두 조건을 모두 만족해야 한다.

1. ET가 있는 방에 도달하려면 반드시 경비가 있는 방을 지나야 한다.
2. 이 성질을 만족하는 다른 어떤 방도 ET가 있는 방에 더 가깝지 않다(그리고 경비는 ET가 있는 방 자체에는 배치할 수 없다).

경비를 배치할 방을 구하라.

첫째 줄에 두 정수 $R$과 $t$가 주어진다. 각각 방의 개수와 ET가 있는 방 번호다. 방은 $0$부터 $R-1$까지 번호가 매겨지며, 모든 손님은 $0$번 방으로 입장한다.

이후 각 줄에는 두 정수 $a$와 $b$가 주어지며, 방 $a$에서 방 $b$로 향하는 일방통행 에어록을 나타낸다($a$에서 $b$로만 지날 수 있다). 문 목록은 입력의 끝까지 이어진다.

다음과 같이 한 줄을 출력한다.

Put guards in room N.

여기서 $N$은 경비를 배치하기로 한 방 번호다.

아래 그림은 예시 시설의 구조를 나타낸다.