우리를 인도하는 넥타이

이제 로봇 판매 수익으로 조수를 고용했으니, 드디어 CEOI 메달이 든 금고를 찾아갈 차례입니다!

금고는 $N$개의 방과 $N - 1$개의 문으로 이어진 대학 건물 안에 있습니다. 모든 방은 다른 모든 방에서 도달할 수 있고, 각 방에는 문이 최대 $3$개 있습니다. 당신과 조수는 각자 건물 평면도를 갖고 있습니다. 두 평면도는 같은 구조를 나타내지만, 방과 문의 번호는 서로 다를 수 있습니다.

두 번째 경기일에는 위원회가 질의 요청을 처리합니다. 이 시간을 틈타 아무에게도 들키지 않고 금고에 다가갈 수 있습니다.

먼저 조수가 건물을 뒤집니다. 금고가 있는 방을 찾으면 그가 당신을 그곳까지 안내합니다.*

조수는 방마다 비밀 표시를 남깁니다. 표시는 넥타이이고, 넥타이는 서로 구별되지 않으므로 당신이 얻는 정보는 각 방에 놓인 넥타이 개수뿐입니다. 한 방에 놓이는 넥타이의 최대 개수는 가능한 한 작아야 합니다(아래 채점 항목 참고).

나중에 화장실에 간다는 핑계로 몰래 빠져나와 남겨진 넥타이를 따라 금고 방을 찾습니다. 금고는 숨겨져 있어서 방에 들어간다고 바로 알아볼 수 없고, 발견한 넥타이에 의존해야 합니다. 자리를 비운 사실이 들키면 안 되므로 금고를 빨리 찾아야 합니다. 시작 위치에서 금고 방까지 가는 직접 경로의 문 개수를 $d$라고 할 때, 지나는 문은 최대 $d + 30$개여야 합니다. 같은 문을 여러 번 지나면 지날 때마다 셉니다.

다음을 수행하는 프로그램을 작성하십시오.

• 조수가 각 방에 남길 넥타이 개수를 알려준다.
• 나중에 금고 방까지 안내한다.

* 결국 금고는 직접 열고 싶지 않나요? 대회가 끝난 뒤 다른 사람이 열어서 메달을 건네받는다면 재미가 없겠죠!