미술품 복원
시간 제한2초메모리 제한128 MB
두 실험실 중 하나에 속한 작업들의 DAG가 주어질 때, 위상 순서를 정해 실험실 전환 횟수를 최소화하는 문제입니다.
문제
바이트랜드에서 가장 유명한 그림 — 레오나르도 다 비트치가 그린, 컴퓨터 마우스를 든 여인의 초상화 — 을 복원해야 한다. 복원 작업은 고도로 전문화된 두 개의 실험실에서 진행된다. 복원 과정은 여러 단계로 나뉘어 있으며, 각 단계마다 그 작업을 수행할 실험실이 정해져 있다.
그림은 매우 귀중하고 손상되기 쉬우므로, 실험실 사이로 그림을 옮기는 일은 위험을 더하며 가능한 한 피해야 한다. 이상적으로는 한 실험실에서 해야 할 모든 작업을 먼저 끝낸 뒤에야 그림을 다른 실험실로 옮기는 것이 좋다. 그러나 단계들 사이에는 선후 관계가 존재한다. 즉, 어떤 단계는 다른 단계가 시작되기 전에 반드시 완료되어야 한다. 그림을 한 실험실에서 다른 실험실로 옮기는 횟수가 최소가 되도록 복원 단계의 순서를 정하는 것이 목표이다. 복원은 두 실험실 중 어느 쪽에서 시작해도 된다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 각 테스트 케이스가 주어진다.
각 테스트 케이스의 첫째 줄에는 공백으로 구분된 두 정수 n과 m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 1 000 000)이 주어진다. n은 복원 단계의 수, m은 단계들 사이의 선후 관계의 수이다. 다음 줄에는 공백으로 구분된 n개의 정수가 주어진다. 그중 i번째 값은 i번째 단계가 첫 번째 실험실에서 진행되면 1, 그렇지 않으면 2이다. 이어지는 m개의 줄에는 각각 두 정수 i와 j (1 ≤ i, j ≤ n)가 주어지며, 이는 i번째 단계가 j번째 단계보다 먼저 완료되어야 함을 뜻한다.
모든 선후 관계를 만족하도록 단계의 순서를 항상 정할 수 있음이 보장된다.
출력
각 테스트 케이스마다, 그림을 두 실험실 사이로 옮겨야 하는 최소 횟수를 한 줄에 하나씩 출력한다. 답은 입력에 주어진 테스트 케이스 순서대로 출력한다.