고고학자 철수는 악어의 신비한 지하 도시를 탐험하다가 위험을 느끼고 도망치게 되었다.

지하 도시는 N개의 방으로 구성되어 있다.

방들을 연결하는 M개의 복도가 있는데, 각 복도는 서로 다른 두 방을 연결하며, 같은 쌍의 방을 연결하는 복도는 최대 1개이다.

복도를 통과하는데 걸리는 시간은 복도마다 다를 수 있다

N개의 방들 중 K개는 바로 탈출이 가능한 “탈출방”이다.

철수는 최초에 방 0에 있다. 철수는 최대한 빨리 탈출방으로 가려고 한다.

악어 문지기는 철수가 탈출하는 것을 막으려고 한다.

문지기는 복도 중 임의의 하나를 막을 수 있는 방법이 있다. 어떤 시점이든 단 하나만 막을 수 있다.

즉, 문지기가 새로운 복도를 막으면 이전에 막았던 복도는 열린다.

철수의 상황을 좀더 자세히 설명하면 다음과 같다:

철수가 어떤 방을 떠나려고 할 때 문지기는 그 방과 연결된 복도들 중 하나를 막을 수 있다.

철수는 막히지 않은 복도 중 하나를 골라서 다른 방으로 이동한다.

철수가 복도에 일단 들어가고 나면 철수가 이동을 완료할 때 까지는 문지기가 이 복도를 막을 수 없다.

철수가 다른 방에 들어가고 나면 문지기는 (방금 지나온 복도도 당연히 포함하여) 또 다른 복도를 막을 수 있고, 이런 식으로 반복된다.

철수는 탈출 계획을 미리 정해 놓기를 원한다.

정확히 말하자면, 각 방 마다, 그 방에 도착하면 어떤 식으로 행동해야 하는 지의 계획이 미리 정해져 있어야 한다.

A가 어떤 방이라고 하자. 만약 A가 탈출방이라면 바로 탈출하면 되므로 별다른 계획이 필요하지 않다.

A가 탈출방이 아니라면 A에 대해서는 다음 중 한가지 형태의 계획이 있어야 한다.

● 만약 A에 있다면 방 B로 이동하는 것이 우선이다. 만약 그 쪽 복도가 막혀 있으면 방 C로 이동하라. ● 이 계획 하에서는 A에 절대 도달할 수 없으므로, 아무 계획이 없음.

어떤 경우에는 (예를 들어 어떤 계획하에서 철수가 싸이클을 도는 경우 등) 문지기가 탈출이 영원히 불가능하도록 만들 수도 있다는 점에 주의하라.

어떤 탈출 계획이 문지기가 어떤 작전을 쓰던지 철수가 유한한 시간 안에 탈출하는 것이 가능하다는 것을 보장하면

그 계획은 "좋은" 계획이라고 부른다.

어떤 좋은 계획 하에서, 철수가 그 시간이 지난 후에는 반드시 탈출한다고 보장할 수 있는 최소의 시간을 T라고 하자.

그 경우, 그 좋은 계획의 “탈출 시간”은 T라고 말한다.

당신은 좋은 계획이 존재하는 탈출 시간의 최소값 T를 구해야 한다.

[예제분석]

방들은 원으로 표시되었고 복도는 줄로 표시되어 있다.

탈출방들은 굵은 원으로 표시되어 있다.

초기에 철수는 (삼각형으로 표시된) 방 0 에 있다. 최적의 탈출 계획 중 하나는 다음과 같다.

● 방 0 에 있다면, 방 1 로 이동하는 것이 우선이다. 만약 그 방향이 막혀 있으면 방 2 로이동하라.

● 방 2 에 있다면, 방 3 으로 이동하는 것이 우선이다. 만약 그 방향이 막혀 있으면 방 4 로 이동하라.

최악의 경우에 시간 7 을 쓰고 탈출방에 도달할 수 있다. 따라서, travel_plan 은 7 을 리턴해야 한다.

가능한 최적의 계획들 중 하나는 다음과 같다.

● 방 0 에 있으면 방 3 으로 이동하는 것이 우선이다. 만약 그 방향이 막혀 있으면 방 2 로 이동하라

● 방 2 에 있으면 방 3 으로 이동하는 것이 우선이다. 만약 그 방향이 막혀 있으면 방 1 로 이동하라

● 방 4 에는 가는 경우가 없으므로 아무 계획이 없다.

이 계획을 이용하면 철수는 시간 14 를 쓴 이후에는 반드시 탈출할 수 있다.

따라서 travel_plan 은 14 를 리턴해야 한다

악어의 지하 도시(crocodile) timer 2초 memory 256MB

악어의 지하 도시(crocodile) 2초 256MB