UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3169. [Cerc2012]Conservation

Statistics 下载数据

Description

在一个Byteland上有一副非常有名的图画需要被封存。这个作品需要在2个实验室进行处理。这个处理过程被分为许多步骤。对于每个步骤,我们知道它必须要在哪个实验室进行。
在两个实验室之间运输这些这些美丽但又易碎的画会带来额外的风险,因此这个运输的过程需要尽可能的被避免。理想情况下所有的工作都会在第一个实验室做完,然后剩下的在另一个实验室完成,但是有些步骤必须在另一步骤完成之后才能完成。你的任务是找到一个工作的顺序,让这个被运输的过程最少。输出需要运输的次数。

Input

第一行N和M,代表着N个步骤,和M个先后关系。下面一行N个数字,第I个数字是1或2,代表了第I个工作需要在哪个实验室完成,下面M行I,J,代表了第I个工作必须在第J个工作前完成。保证必有解

Output

 
输出最少需要的运输次数。

Sample Input


5 6
1 2 1 2 1
1 2
1 3
2 4
3 4
2 5
3 5

Sample Output


2

Hint



100%数据中n<=100000,m<=1000000。

Source