정올국에는 N개의 지역(시/군)이 있고, 각 지역마다 생산하는 특산물이 다르다.

또한 정올국에는 두 지역을 잇는 M개의 도로가 있다. 각 도로의 길이(거리)는 각각 다르다. 도로는 항상 양방향 통행 가능하다.

각 지역은 항상 한가지의 특산물만 생산한다.

그러므로 그 외의 다른 특산물을 얻기 위해서는 다른 지역과 교역(지방끼리의 무역)을 해야 한다.

당연히 교역은 서로 다른 특산물을 생산하는 지역끼리만 시행하게 된다.

두 지역에서 생산하는 특산물이 서로 다르다면, 두 지역은 항상 교역이 가능하다.

두 지역이 서로 교역을 하게 된다면, 교역 경로는 항상 두 지역간의 최단경로로만 이루어진다.

따라서 정올국에서 가장 활발히 교역하는 두 지역은, 서로 다른 특산물을 생산하면서 두 지역간의 최단 거리가 가장 짧은 두 지역이다.

정올국의 대통령인 상준이는 가장 활발히 교역하는 두 지역간의 최단 거리가 궁금해졌다.

사실 이를 구하는 것은 어렵지 않다.

문제는 어떤 지역은 시간이 흐름에 따라 생산하는 특산물을 바꾸기도 한다는 것이다.

그 순간 가장 활발히 교역하는 두 지역간의 최단 거리 역시 바뀔 수 있다.

따라서 상준이는 이에 대비한 프로그램을 만드는 것을 정보왕인 당신에게 부탁하기로 하였다.

시간 순서대로, 어떤 지역에서 생산하는 특산물이 바뀔 때마다, 가장 활발히 교역하는 두 지역간의 최단거리를 출력해 주는 프로그램을 작성하라.

교역 timer 1s memory 256MB

교역 1s 256MB