eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Співпроцесор

Співпроцесор

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Вам дана програма, яка складається з набору задач. Задачі організовані в орієнтований ациклічний граф залежностей: кожна задача може залежати від результатів виконання одної або декількох інших задач і в графі немає орієнтованих циклічних залежностей між задачами. Задача може бути виконана тільки після виконання всіх задач, від яких вона залежить.

Деякі задачі в графі повинні виконуватися на співпроцесорі, інші – на головному процесорі. За один виклик співпроцесора ви можете передати йому список задач, які повинні виконатися на ньому. Для кожної задачі зі списку, всі задачі, від яких вона залежить, повинні уже бути виконані або знаходитися в цьому ж списку. Головний процесор починає виконання програми і автоматично отримує результати виконання задач від співпроцесора.

Знайдіть мінімальну кількість викликів співпроцесора, необхідних для виконання програми.

Вхідні дані

Перший рядок містить два числа N і M (1N, M2·10^5) – кількість задач і кількість залежностей між ними.

Другий рядок містить N чисел E[i] ∈ {0,1}, розділених пробілами. Якщо E[i] = 0, то задача i повинна виконатися на головному процесорі, інакше – на співпроцесорі.

Наступні M рядків описують залежності між задачами. Кожний з рядків містить по два числа T[1] і T[2], що означає, що задача T[1] залежить від задачі T[2] (T[1]T[2]). Задачі пронумеровані від 0 до N-1. Всі M пар різні.

Вихідні дані

Виведіть одне число – мінімальна кількість викликів співпроцесора, необхідна для виконання програми.

Приклад

Вхідні дані #1
4 3
0 1 0 1
0 1
1 2
2 3
Вихідні дані #1
2
Вхідні дані #2
4 3
1 1 1 0
0 1
0 2
3 0
Вихідні дані #2
1