보조 프로세서

실행하려는 프로그램이 의존성 그래프로 구성된 작업 집합으로 주어진다. 의존성 그래프는 방향 비순환 그래프이다. 각 작업은 하나 또는 여러 다른 작업의 결과에 의존할 수 있으며, 작업 사이에는 방향 순환 의존성이 없다. 어떤 작업은 자신이 의존하는 모든 작업이 이미 완료된 경우에만 실행할 수 있다.

그래프의 작업 중 일부는 보조 프로세서에서만 실행할 수 있고, 나머지는 메인 프로세서에서만 실행할 수 있다. 보조 프로세서를 한 번 호출할 때 그 프로세서에서만 실행할 수 있는 작업들의 집합을 보낼 수 있다. 집합의 각 작업에 대해, 그 작업이 의존하는 모든 작업은 이미 완료되었거나 해당 집합에 포함되어 있어야 한다. 메인 프로세서가 프로그램 실행을 시작하며, 보조 프로세서에서 실행된 작업의 결과는 자동으로 받는다.

주어진 프로그램을 실행하는 데 필요한 보조 프로세서 호출 횟수의 최솟값을 구한다.

첫째 줄에는 공백으로 구분된 두 정수 N (1 ≤ N ≤ 105)와 M (0 ≤ M ≤ 105)가 주어진다. 각각 주어진 작업의 총개수와 작업 사이의 의존 관계 총개수를 나타낸다.

다음 줄에는 공백으로 구분된 N개의 정수 가 주어진다. If Ei = 0이면 작업 i는 메인 프로세서에서만 실행할 수 있으며, 그렇지 않으면 보조 프로세서에서만 실행할 수 있다.

다음 M개의 줄에는 작업 사이의 의존 관계가 주어진다. 각 줄에는 공백으로 구분된 두 정수 T1 and T2가 주어지며, 이는 작업 T1가 작업 T2 (T1 ≠ T2)에 의존한다는 뜻이다. 작업의 인덱스는 0부터 N - 1까지이다. All M개의 순서쌍 (T1, T2)은 서로 다르다. 작업 사이에 순환 의존성이 없다는 것이 보장된다.

프로그램을 실행하는 데 필요한 보조 프로세서 호출 횟수의 최솟값인 정수를 한 줄에 출력한다.

첫 번째 테스트에서 작업 1과 3은 보조 프로세서에서만 실행할 수 있다. 의존성 그래프가 선형이므로 작업은 3 -> 2 -> 1 -> 0 순서로 실행해야 한다. 보조 프로세서를 두 번 호출해야 한다. 처음에는 작업 3을 위해 호출하고, 이어서 메인 프로세서에서 작업 2를 실행한 다음, 작업 1을 위해 호출하고, 마지막으로 메인 프로세서에서 작업 0을 실행한다.

두 번째 테스트에서 작업 0, 1, 2는 보조 프로세서에서만 실행할 수 있다. 작업 1과 2에는 의존 관계가 없고 작업 0은 작업 1과 2에 의존하므로, 세 작업 0, 1, 2를 모두 보조 프로세서 호출 한 번으로 보낼 수 있다. 그 후 작업 3을 메인 프로세서에서 실행한다.