#2056. 「TJOI / HEOI2016」序列

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

输入格式

输入的第一行有两个正整数 n, m ,分别表示序列的长度和变化的个数。
接下来一行有 n 个数,表示这个数列原始的状态。
接下来 m 行,每行有两个数 x, y ,表示数列的第 x 项可以变化成 y 这个值。

输出格式

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

样例

样例输入

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

样例输出

3

样例解释

注意:每种变化最多只有一个值发生变化。

在样例输入中,所有的变化是:

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

选择子序列为原序列,即在任意一种变化中均为不降子序列。

数据范围与提示

对于所有的数据, 1 \leq x \leq n ,所有数字均为正整数,且小于等于 100000