给您一个程序,您想要将其作为一组以依赖关系图形式组织的任务来执行。依赖图是一种有向无环图:每个任务可以依赖于一个或多个其他任务的结果,并且任务之间不存在有向循环依赖关系。仅当一个任务所依赖的所有任务都已完成时,该任务才能被执行。
图中的某些任务只能在协处理器上执行,其余任务只能在主处理器上执行。在一个协处理器调用中,您可以向其发送一组只能在其上执行的任务。对于集合中的每个任务,它所依赖的所有任务必须已经完成或包含在集合中。主处理器开始执行程序并自动获取协处理器上执行的任务的结果。
查找执行给定程序所需的协处理器调用的最小数量。
输入
第一行包含两个以空格分隔的整数 N (1 ≤ N ≤ 105) — 给定的任务总数,M (0 ≤ M ≤ 105) — 任务之间的依赖关系总数。
下一行包含 N 个空格分隔的整数 $${ E _ { i } \in \{ 0, 1 \} }$$。如果Ei = 0,则任务i只能在主处理器上执行,否则只能在协处理器上执行。
接下来的 M 行描述了任务之间的依赖关系。每行包含两个空格分隔的整数 T1 和 T2,意味着任务 T1 依赖于任务 T2(T1 ≠ T2)。任务索引从 0 到 N - 1。所有 M 对(T1、T2)都是不同的。保证任务之间不存在循环依赖。
输出
输出一行包含一个整数 — 执行程序所需的协处理器调用的最少数量。
示例
输入 #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
注意
在第一个测试中,任务 1 和 3 只能在协处理器上执行。依赖图是线性的,因此任务必须按照 3 -> 2 -> 1 -> 0 的顺序执行。您必须调用协处理器两次:首先为任务 3 调用它,然后在主处理器上执行任务 2,然后为任务 1 调用它,最后在主处理器上执行任务 0。
在第二个测试中,任务 0、1 和 2 只能在协处理器上执行。任务 1 和 2 没有依赖性,任务 0 依赖于任务 1 和 2,因此所有三个任务 0、1 和 2 都可以在一个协处理器调用中发送。之后任务3在主处理器上执行。