수질 오염

허리케인으로 생기는 초기 피해는 주로 비와 진흙, 그리고 그 직접적인 영향(특히 익사)에서 비롯된다. 하지만 허리케인의 장기적 위험 가운데 일부는 수질 오염과 질병에서 나온다. 물이 불어나면 평소 보관되던 곳에서 위험한 하수나 기타 오염 물질이 사람이 있는 곳으로 옮겨질 수 있다. 오염된 물을 마시면 당연히 위험하다. 그래서 수위가 올라가더라도 오염 물질을 가두어 두는 것이 중요하다.

이 문제는 다음과 같이 모델링한다. 오염된 장소(하수 처리장, 쓰레기 매립지, 생물 위험 실험실 등)의 목록, 보호해야 할 장소(병원, 도시 수처리장 등)의 목록, 그리고 장소 사이의 연결 정보가 주어진다. 이 연결은 허리케인 중 또는 이후에 침수되어 오염 물질을 옮기는 연결이다. 목표는 모든 중요한 장소를 모든 오염 물질로부터 지키기 위해 차단해야 하는 연결의 최소 개수를 구하는 것이다(예를 들어 큰 모래주머니로 막는 경우).

첫 줄에 데이터 세트의 개수 1 ≤ K ≤ 100이 주어진다. 이어서 K개의 데이터 세트가 아래 형식으로 주어진다.

각 데이터 세트의 첫 줄에는 두 정수 n과 c가 주어진다. 1 ≤ n ≤ 500은 장소의 개수이고, 0 ≤ c ≤ 5000은 연결의 개수이다.

다음 줄에는 장소 i의 종류를 나타내는 정수 n개 0 ≤ t_i ≤ 2가 주어진다. 0은 오염되지도 않고 중요하지도 않은 장소, 1은 오염되었지만 중요하지 않은 장소, 2는 중요한 장소, 즉 반드시 보호해야 하는 장소(오염되어 있지 않음)를 뜻한다.

이어서 c개의 줄에 각각 두 정수 1 ≤ s_j, t_j ≤ n이 주어진다. 이는 s_j와 t_j 사이에 오염 물질이 퍼질 수 있는 연결이 있다는 뜻이며, 연결은 양방향이다.

각 데이터 세트마다 "Data Set x:"를 한 줄에 단독으로 출력한다. x는 데이터 세트 번호이다. 그다음 중요한 장소가 하나도 오염되지 않도록 차단해야 하는 연결의 개수를 출력한다.

각 데이터 세트의 출력 뒤에는 빈 줄을 하나 출력한다.