English · Original
Chinese · Translation
Formal · Original
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.
## Input
The first line contains two space-separated integers _N_ (1 ≤ _N_ ≤ 105) — the total number of tasks given, and _M_ (0 ≤ _M_ ≤ 105) — 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
Output one line containing an integer — the minimal number of coprocessor calls necessary to execute the program.
[samples]
## Note
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.
你被给定一个程序，其任务组织成一个依赖图。依赖图是一个有向无环图：每个任务可能依赖于一个或多个其他任务的结果，且任务之间不存在有向循环依赖。只有当一个任务所依赖的所有任务都已完成时，该任务才能被执行。
图中的一些任务只能在协处理器上执行，其余任务只能在主处理器上执行。在一次协处理器调用中，你可以向其发送一组只能在协处理器上执行的任务。对于该集合中的每个任务，其所有依赖任务必须要么已经完成，要么也包含在该集合中。主处理器启动程序执行，并自动获取协处理器执行任务的结果。
求执行给定程序所需的最少协处理器调用次数。
第一行包含两个用空格分隔的整数 $N$ ($1 ≤ N ≤ 10^5$) —— 任务总数，和 $M$ ($0 ≤ M ≤ 10^5$) —— 任务间的依赖总数。
下一行包含 $N$ 个用空格分隔的整数。若 $E_i = 0$，则任务 $i$ 只能在主处理器上执行；否则，它只能在协处理器上执行。
接下来的 $M$ 行描述任务间的依赖关系。每行包含两个用空格分隔的整数 $T_1$ 和 $T_2$，表示任务 $T_1$ 依赖于任务 $T_2$ ($T_1 ≠ T_2$)。任务编号从 $0$ 到 $N - 1$。所有 $M$ 对 $(T_1, T_2)$ 均互不相同。保证任务间不存在循环依赖。
输出一行，包含一个整数 —— 执行程序所需的最少协处理器调用次数。
在第一个测试用例中，任务 1 和 3 只能在协处理器上执行。依赖图是线性的，因此任务必须按顺序 3 -> 2 -> 1 -> 0 执行。你需要调用协处理器两次：第一次调用协处理器执行任务 3，然后在主处理器上执行任务 2，接着调用协处理器执行任务 1，最后在主处理器上执行任务 0。
在第二个测试用例中，任务 0、1 和 2 只能在协处理器上执行。任务 1 和 2 没有依赖，而任务 0 依赖于任务 1 和 2，因此可以将任务 0、1 和 2 一次性发送到协处理器。之后在主处理器上执行任务 3。
## Input
第一行包含两个用空格分隔的整数 $N$ ($1 ≤ N ≤ 10^5$) —— 任务总数，和 $M$ ($0 ≤ M ≤ 10^5$) —— 任务间的依赖总数。下一行包含 $N$ 个用空格分隔的整数。若 $E_i = 0$，则任务 $i$ 只能在主处理器上执行；否则，它只能在协处理器上执行。接下来的 $M$ 行描述任务间的依赖关系。每行包含两个用空格分隔的整数 $T_1$ 和 $T_2$，表示任务 $T_1$ 依赖于任务 $T_2$ ($T_1 ≠ T_2$)。任务编号从 $0$ 到 $N - 1$。所有 $M$ 对 $(T_1, T_2)$ 均互不相同。保证任务间不存在循环依赖。
## Output
输出一行，包含一个整数 —— 执行程序所需的最少协处理器调用次数。
[samples]
## Note
在第一个测试用例中，任务 1 和 3 只能在协处理器上执行。依赖图是线性的，因此任务必须按顺序 3 -> 2 -> 1 -> 0 执行。你需要调用协处理器两次：第一次调用协处理器执行任务 3，然后在主处理器上执行任务 2，接着调用协处理器执行任务 1，最后在主处理器上执行任务 0。
在第二个测试用例中，任务 0、1 和 2 只能在协处理器上执行。任务 1 和 2 没有依赖，而任务 0 依赖于任务 1 和 2，因此可以将任务 0、1 和 2 一次性发送到协处理器。之后在主处理器上执行任务 3。
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of tasks, indexed from $ 0 $ to $ N-1 $.
Let $ M \in \mathbb{Z}_{\geq 0} $ be the number of dependencies.
Let $ E = (e_0, e_1, \dots, e_{N-1}) \in \{0,1\}^N $, where $ e_i = 1 $ iff task $ i $ requires the coprocessor.
Let $ G = (V, D) $ be a directed acyclic graph (DAG), where $ V = \{0, 1, \dots, N-1\} $, and $ D \subseteq V \times V $ is the set of directed edges: $ (t_1, t_2) \in D $ means task $ t_1 $ depends on task $ t_2 $ (i.e., $ t_2 \to t_1 $).
**Constraints**
1. $ 1 \leq N \leq 10^5 $
2. $ 0 \leq M \leq 10^5 $
3. $ G $ is acyclic.
4. For each edge $ (t_1, t_2) \in D $, task $ t_1 $ cannot be executed until task $ t_2 $ is completed.
5. Tasks with $ e_i = 0 $ run on the main processor; those with $ e_i = 1 $ must run on the coprocessor.
6. In one coprocessor call, a subset $ S \subseteq \{ i \mid e_i = 1 \} $ can be submitted iff for every $ i \in S $, all predecessors $ j $ of $ i $ (i.e., $ (i,j) \in D $) satisfy: either $ j \notin S $ and $ j $ is already completed, or $ j \in S $.
**Objective**
Find the minimum number of coprocessor calls required to execute all tasks, under the constraint that a coprocessor call may include multiple coprocessor tasks as long as their dependencies (within the set or already completed) are satisfied.
API Response (JSON)
{
"problem": {
"name": "E. Coprocessor",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF909E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一个程序，其任务组织成一个依赖图。依赖图是一个有向无环图：每个任务可能依赖于一个或多个其他任务的结果，且任务之间不存在有向循环依赖。只有当一个任务所依赖的所有任务都已完成时，该任务才能被执行。\n\n图中的一些任务只能在协处理器上执行，其余任务只能在主处理器上执行。在一次协处理器调用中，你可以向其发送一组只能在协处理器上执行的任务。对于该集合中的每个任务，其所有依赖任务必须要么已经完成，要么也...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ N \\in \\mathbb{Z}^+ $ be the number of tasks, indexed from $ 0 $ to $ N-1 $. \nLet $ M \\in \\mathbb{Z}_{\\geq 0} $ be the number of dependencies. \nLet $ E = (e_0, e_1, \\dots, e_{...",
"is_translate": false,
"language": "Formal"
}
]
}