아날로그 클러스터

면접 대비

시간 제한1초메모리 제한512 MB

요약

n개 피아노에 각각 폭이 주어지고 c개의 연결이 있을 때, 연결된 두 피아노의 폭이 같아지도록 바꿔야 하는 피아노 수의 최솟값을 구한다.

문제

분산 시스템을 주제로 학위 논문을 쓰는 Drew는 아직 개척되지 않은 시장에 눈을 돌렸다. 바로 자동 연주 피아노(player piano)다. 이 아날로그 기기는 적당한 재질과 너비의 종이를 넣으면 그 종이에 복사된 곡을 무엇이든 연주한다.

Drew는 이 기기들을 네트워크로 연결하려고 한다. 기기들은 원래 쓰는 매체인 긴 종이를 통해 통신하게 된다.

문제는 바로 생겼다. 피아노는 같은 너비의 종이를 받는 경우에만 직접 통신할 수 있는데, 컴퓨터과학과에 있는 피아노가 모두 같은 너비의 종이를 쓰지는 않는다. 계획을 성공시키려면 일부 피아노는 개조해야 한다.

시간은 소중하고, 특히 Drew가 고용한 값비싼 기술자의 시간은 눈이 튀어나올 만큼 소중하다. 프로젝트가 작동하게 하려면 피아노를 최소 몇 대 개조하면 되는가?

첫째 줄에 피아노의 수 n (1 ≤ n ≤ 1000)과 피아노 사이의 연결 수 c (1 ≤ c ≤ 105)가 주어진다.
둘째 줄에 각 피아노가 받는 종이의 너비를 센티미터 단위의 정수로 순서대로 w1부터 wn까지 (1 ≤ w ≤ 106) 준다.
다음 c개 줄은 모두 서로 다르며, 각 줄에는 피아노 a와 b가 호환되어야 함을 나타내는 두 정수 a, b (1 ≤ a < b ≤ n)가 주어진다.

모든 연결이 가능해지도록 개조할 수 있는 피아노의 최소 대수를 출력한다.