| Codeforces Round 455 (Div. 2) |
|---|
| Закончено |
Вам дана программа, состоящая из набора задач. Задачи организованы в ориентированный ациклический граф зависимостей: каждая задача может зависеть от результатов выполнения одной или нескольких других задач, и в графе нет ориентированных циклических зависимостей между задачами. Задача может быть выполнена только после завершения всех задач, от которых она зависит.
Некоторые задачи в графе должны выполняться на сопроцессоре, остальные — только на главном процессоре. За один вызов сопроцессора вы можете передать ему список задач, которые должны выполниться на нем. Для каждой задачи из списка все задачи, от которых она зависит, должны быть либо уже выполнены на момент вызова сопроцессора, либо находиться в этом же списке. Главный процессор начинает выполнение программы и автоматически получает результаты выполнения задач от сопроцессора.
Найдите минимальное количество вызовов сопроцессора, необходимых для выполнения программы.
Первая строка входных данных содержит два целых числа, разделенных пробелом: N (1 ≤ N ≤ 105) — общее количество задач и M (0 ≤ M ≤ 105) — общее количество зависимостей между задачами.
Вторая строка содержит N целых чисел 
, разделенных пробелами. Если Ei = 0, задача i должна выполняться на главном процессоре, иначе — на сопроцессоре.
Следующие M строк описывают зависимости между задачами. Каждая строка содержит два целых числа, разделенных пробелами, T1 и T2 и означает, что задача T1 зависит от задачи T2 (T1 ≠ T2). Задачи пронумерованы от 0 до N - 1. Все M пар (T1, T2) различны. Гарантируется, что циклических зависимостей между задачами нет.
Выведите одно число — минимальное количество вызовов сопроцессора, необходимых для выполнения программы.
4 3
0 1 0 1
0 1
1 2
2 3
2
4 3
1 1 1 0
0 1
0 2
3 0
1
В первом примере задачи 1 и 3 должны выполняться на сопроцессоре. Граф зависимостей линейный, и задачи должны выполняться в порядке 3 -> 2 -> 1 -> 0. Необходимо два вызова сопроцессора: за первый вызов выполняется задача 3, затем выполняется задача 2 на главном процессоре, за второй вызов выполняется задача 1 и наконец выполняется задача 0 на главном процессоре.
Во втором примере задачи 0, 1 и 2 должны выполняться на сопроцессоре. У задач 1 и 2 нет зависимостей, а задача 0 зависит только от задач 1 и 2, поэтому все три задачи 0, 1 и 2 можно выполнить за один вызов сопроцессора. После этого задача 3 выполняется на главном процессоре.
