/ WHOJ / 题库 /

文物

文物

题目描述

考古学家刚刚出土了一件瓷瓶,但瓷瓶很多地方需要修补。

这个瓷瓶被政府要求在 22 个实验室进行复原。这个处理过程被分为许多步骤,给两个实验室分别处理。但是有些步骤必须在另一步骤完成之后才能完成。如果完成一个步骤后,必须要到另一个实验室进行复原,那么我们把这个运输次数加 11。你的任务是找到一个复原的顺序,让这个被运输的过程最少。

格式

输入格式

第一行 NNMM,代表着 NN 个步骤,和 MM 个先后关系。下面一行 NN 个数字,第 ii 个数字是 1122,代表了第 ii 个工作需要在哪个实验室完成,下面 MMi,ji,j,代表了第 ii 个工作必须在第 jj个工作前完成。
你可以认为这个题目必有解。

输出格式

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

样例1

输入样例1

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

输出样例1

提示

因为本题数据较大,如果出现后面几个点突然 TLETLE,可以多尝试几次,如果多尝试几次还 TLETLE,应该是代码问题。

限制

30%30\% 数据保证 n<=5n<=5
100%100\% 数据中 n<=100000m<=1000000n<=100000,m<=1000000