Coprocessor#8785
You are given a program composed of a set of tasks. These tasks are arranged in a directed acyclic graph (DAG) of dependencies: each task may rely on the results of one or more other tasks, and there are no circular dependencies among them. A task can only be executed once all the tasks it depends on have been completed.
Some tasks in the graph must be executed on a coprocessor, while others must be executed on the main processor. With a single call to the coprocessor, you can pass it a list of tasks that need to be executed there. For each task in this list, all its dependencies must have already been completed or be included in the same list. The main processor begins executing the program and automatically receives the results of task execution from the coprocessor.
Your goal is to determine the minimum number of coprocessor calls needed to execute the entire program.
The first line contains two integers and (1 \le N, M \le 2 \cdot 10^5) – representing the number of tasks and the number of dependencies between them, respectively.
The second line contains integers E_i \in \{0,1\}, separated by spaces. If E_i = 0, task must be executed on the main processor; if E_i = 1, it must be executed on the coprocessor.
The following lines describe the dependencies between tasks. Each line contains two integers T_1 and T_2, indicating that task T_1 depends on task T_2 (T_1 \ne T_2). Tasks are numbered from to N-1. All pairs are unique.
Print a single integer – the minimum number of coprocessor calls required to execute the program.
Example 1
Example 2