1 부터 n까지 번호가 붙은 n개의 비행 가능한 지역이 있다.

각 지역은 특수한 지형 때문에 i번 지역을 비행하려면 최소 고도 a[i]를 지켜야 한다.

또한 탁월풍(어느 한 지역에서 일정 기간 동안 가장 우세하게 나타나는 바람)의 영향으로 특정 지역 쌍들 사이만 비행할 수 있다.

1부터 m까지 번호가 매겨진 m개의 지역 쌍이 있다. j번째 쌍은 u[j]와 v[j]를 가지는데 이는 u[j]지역과 v[j]지역을 양방향으로 다닐 수 있다는 의미이다.

이 쌍들을 이용하여 어떤 지역에서 출발하든 다른 모든 지역으로 도착할 수 있음이 보장된다.

처음에는 1번 지역의 고도 0에 있으며, n번 지역으로 이동하고 싶으며, n번 지역의 고도 0으로 착륙해야 한다.

1분 이 경과하면 현재 지역에 머물거나 다른 지역으로 떠날 수 있고 동시에 고도를 1증가하거나 1감소하거나 유지할 수 있다.

그러나 지역에 도착하면 고도는 최소 고도 이상이어야 한다. 1번 지역에서 이륙하여 n번 지역에 착륙하는 최소 시간을 구하라.

비행 timer 1s memory 1024MB

비행 1s 1024MB