#1994. [HEOI2016/TJOI2016] 序列

[HEOI2016/TJOI2016] 序列

题目描述

佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给她。

玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性,她想请教你,能否选出一个子序列,使得在任意一种变化和原序列中,这个子序列都是不降的?请你告诉她这个子序列的最长长度即可。

输入格式

输入的第一行有两个正整数 n,mn,m,分别表示序列的长度和变化的个数。

接下来一行有 nn 个整数,表示这个数列原始的状态。

接下来 mm 行,每行有 22 个整数 x,yx,y,表示数列的第 xx 项可以变化成 yy 这个值。

输出格式

输出一个整数,表示对应的答案。

样例

3 4 
1 2 3 
1 2 
2 3 
2 1 
3 4
3

题目来源:洛谷 P4093