유명한 식물원 중에 하나인 KOI식물원의 연구원인 범준이는 최근 식물원에 여러 종류의 허브를 재배하며 실험하게 되었다.

허브를 심을 때는 주의할 점이 있는데 서로 다른 종류의 허브 사이에는 종의 보존과 안정된 성장을 위하여 최소한의 여유간격이 필요하다고 한다.

KOI식물원은 N(1 <= N <= 200,000)개의 필드와 필드 사이를 양방향으로 연결하는 M(1 <= M <= 200,000)개의 통로가 있다.

이 통로들을 이용하면 어느 필드에서든 다른 임의의 특정 필드로 이동할 수 있다.

한 통로의 길이는 1 ~ 1,000,000 이고 임의의 두 필드를 직접 연결하는 통로의 개수는 많아야 한 개뿐이다.

범준이는 초기에 K(1<=K<=N)종류의 허브를 심는다. 하지만 시간이 지나면서 한 필드의 허브를 다른 종류로 바꾸어 재배할 수도 있다.

이 과정을 범준이는 “업뎃”이라고 부른다. 그리고 업뎃은 누적되어 적용된다.

범준이는 종의 보존과 안정된 성장을 위하여 각각의 업뎃 이후 서로 다른 종류의 허브간 거리 중에 최소값이 얼마인지 알고자 한다.

이 값이 클수록 종의 보존과 안정된 성장에 유리하기 때문이다.

식물원에는 적어도 2종류 이상의 서로 다른 허브가 있다는 것이 보장된다고 한다.

입력 데이터의 30%는 각 필드에 연결된 통로의 개수가 많아야 10개이다.

식물원 timer 2s memory 512MB

식물원 2s 512MB