말나르 씨는 여행을 떠났다. 그가 여행하려고 결정한 나라는 n 개의 도시와 그들을 연결하는 m 개의 양방향 도로로 나타낼 수 있다. 각 도로의 길이는 동일하며, 이 도로를 통해 어떤 도시에서든 다른 도시로 이동할 수 있다. 도시 a에서 도시 b로의 경로는 a에서 시작하여 그 순서대로 도로를 순차적으로 이동하여 b 도시에 도달하는 도로들로 정의된다. 경로의 길이는 해당 경로 상의 도로 수로 정의된다.

말나르 씨는 규칙적으로 한 도시에서 가장 비싼 호텔을 예약한 다음 여행 계획을 시작했다. 계획을 용이하게하기 위해 호텔에서 각 도시까지 필요한 최단 경로의 길이를 기록했다.

오래 기다렸던 여행에 기대감이 커져 말나르 씨는 호텔이 어느 도시에 있는지 완전히 잊어 버렸다. 말나르씨를 위해 호텔이 위치할 수 있는 도시를 추측하는 프로그램을 작성하시오.

#7074 upload 117 done 15 how_to_reg 12 call_split 서브태스크

여행 timer 2s memory 1024MB

#7074
서브태스크

여행 2s 1024MB