용주는 우연히 산에서 보물을 하나 주웠다. 용주는 이 보물을 외딴 섬에 있는 동굴에 숨기기로 했다.

동굴은 크게 N개의 방이 있으며, N-1개의 통로로 이루어져 있다.

어떤 방에서든 모든 방으로 갈 수 있는 경로가 유일하게 존재한다.

x번 방과 y번 방의 거리란, x번 방에서 y번 방으로 가는 경로상에 있는 통로의 수라고 정의하도록 하자.

용주는 최근 보물찾기 1등을 달리고 있는 통칭 “해적형제” 의영-재영 형제가 동굴에서 보물을 찾을 때,

각각 두 가지 방식으로 찾는다는 것을 알아냈다.

탐색 방식은 아래와 같다.

- 의영이는 입구(1번 방)에서의 거리가 가장 가까운 방 순서대로 수색하되, 거리가 같은 방끼리는 번호가 작은 방부터 수색한다.

- 재영이는 입구(1번 방)에서의 거리가 가장 가까운 방 순서대로 수색하되, 거리가 같은 방끼리는 번호가 큰 방부터 수색한다.

- 방 하나를 탐색하는데는 1시간이 걸리며, 통로로 이동하는 시간은 너무 미미하므로 무시한다.

의영이와 재영이는 둘 중 한 명이 이미 탐색을 마친 방은 탐색하지 않고 다음 순서로 넘어간다.

- 동시에 같은 방을 탐색하게 될 경우엔 의영이가 맡게 되고 재영이는 다음 순서로 넘어간다.

예를 들어 그림 1과 같은 동굴이 있다고 하자.

그림 1

우선 탐색 방식의 이해를 돕기 위해, 의영이만 혼자 보물을 찾는다고 가정할 때 탐색 순서는

1->2->3->4->5->6->7->8이며, (1->2->3->4->5->6->8->7이 아님에 유의한다.)

재영이의 경우 1->4->3->2->8->7->6->5이다.

따라서 둘이 같이 탐색을 한다면 탐색순서는 다음과 같다.

용주는 자신이 보물을 숨긴 동굴에 의영-재영 형제가 도착하더라도 최대한 보물을 찾는데 오래 걸리게 만들어, 자신의 보물을 지킬 시간을 벌려고 한다.

그러려면 위 예의 경우에는 6번 방이나 7번 방에 보물을 숨겨야 최대한 오랜 시간인 4시간 동안 버틸 수 있다.

동굴의 구조가 주어졌을 때, 용주가 의영-재영에게 최대한 오래 버티기 위해 용주가 보물을 숨겨야 하는 최적의 방을 찾아 출력하는 프로그램을 작성하시오.

보물 숨기기 timer 1s memory 256MB

보물 숨기기 1s 256MB