Coprocessor

**题目描述** 给你 $N$ 个任务，任务从 $0$ 开始标号，有些只能用主处理器处理，另外的任务只能用副处理器处理。其中存在 $M$ 个依赖关系，如果任务 $i$ 依赖于任务 $j$，那么称 $j$ 是 $i$ 的前继任务。 主处理器和副处理器都可以一次处理很多个任务。一个任务能被处理的条件为其所有的前继任务已经被执行过了，或者前继任务和自己同时被放进同一个处理器处理。 现在给出这些依赖关系和每个任务处理要用的处理器，求副处理器最少运行了几次。保证依赖关系是一张有向无环图。 **输入格式** 第一行输入两个非负整数 $N, M\ (1 \le N \le 10 ^ 5,\ 0 \le M \le 10 ^ 5)$。 接下来输入一行 $N$ 个整数 $E _ i\ (E _ i \in \{0, 1\})$，若 $E _ i = 0$ 则表示任务 $i$ 只能在主处理器上运行，否则其只能在副处理器上运行。 接下来 $M$ 行，每行两个非负整数 $T _ 1, T _ 2\ (0 \le T _ i < n,\ T _ 1 \ne T _ 2)$，表示任务 $T _ 1$ 依赖于任务 $T _ 2$。 **输出格式** 一行一个整数表示答案。 感谢 @Styx 提供的翻译。

You are given a program you want to execute as a set of tasks organized in a dependency graph. The dependency graph is a directed acyclic graph: each task can depend on results of one or several other tasks, and there are no directed circular dependencies between tasks. A task can only be executed if all tasks it depends on have already completed. Some of the tasks in the graph can only be executed on a coprocessor, and the rest can only be executed on the main processor. In one coprocessor call you can send it a set of tasks which can only be executed on it. For each task of the set, all tasks on which it depends must be either already completed or be included in the set. The main processor starts the program execution and gets the results of tasks executed on the coprocessor automatically. Find the minimal number of coprocessor calls which are necessary to execute the given program.

The first line contains two space-separated integers $ N $ ( $ 1<=N<=10^{5} $ ) — the total number of tasks given, and $ M $ ( $ 0<=M<=10^{5} $ ) — the total number of dependencies between tasks. The next line contains $ N $ space-separated integers . If $ E_{i}=0 $ , task $ i $ can only be executed on the main processor, otherwise it can only be executed on the coprocessor. The next $ M $ lines describe the dependencies between tasks. Each line contains two space-separated integers $ T_{1} $ and $ T_{2} $ and means that task $ T_{1} $ depends on task $ T_{2} $ ( $ T_{1}≠T_{2} $ ). Tasks are indexed from $ 0 $ to $ N-1 $ . All $ M $ pairs $ (T_{1},T_{2}) $ are distinct. It is guaranteed that there are no circular dependencies between tasks.

Output one line containing an integer — the minimal number of coprocessor calls necessary to execute the program.

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

In the first test, tasks 1 and 3 can only be executed on the coprocessor. The dependency graph is linear, so the tasks must be executed in order 3 -> 2 -> 1 -> 0. You have to call coprocessor twice: first you call it for task 3, then you execute task 2 on the main processor, then you call it for for task 1, and finally you execute task 0 on the main processor. In the second test, tasks 0, 1 and 2 can only be executed on the coprocessor. Tasks 1 and 2 have no dependencies, and task 0 depends on tasks 1 and 2, so all three tasks 0, 1 and 2 can be sent in one coprocessor call. After that task 3 is executed on the main processor.