{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e .sampledata { font-family: \"Courier New\", Courier, monospace; white-space: pre; }\u003c/style\u003e\u003cp\u003e\u0026nbsp;佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列,数列中某些项的值\u003c/p\u003e \n\u003cdiv\u003e\n 可能会变化,但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性,她想请教你\n\u003c/div\u003e \n\u003cdiv\u003e\n ,能否选出一个子序列,使得在任意一种变化中,这个子序列都是不降的?请你告诉她这个子序列的最长长度即可\n\u003c/div\u003e \n\u003cdiv\u003e\n 。注意:每种变化最多只有一个值发生变化。在样例输入1中,所有的变化是:\n\u003c/div\u003e \n\u003cdiv\u003e\n 1 2 3\n\u003c/div\u003e \n\u003cdiv\u003e\n 2 2 3\n\u003c/div\u003e \n\u003cdiv\u003e\n 1 3 3\n\u003c/div\u003e \n\u003cdiv\u003e\n 1 1 31 2 4\n\u003c/div\u003e \n\u003cdiv\u003e\n 选择子序列为原序列,即在任意一种变化中均为不降子序列在样例输入2中,所有的变化是:3 3 33 2 3选择子序列\n\u003c/div\u003e \n\u003cdiv\u003e\n 为第一个元素和第三个元素,或者第二个元素和第三个元素,均可满足要求\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\u0026nbsp;输入的第一行有两个正整数n, m,分别表示序列的长度和变化的个数。接下来一行有n个数,表示这个数列原始的\u003c/p\u003e \n\u003cdiv\u003e\n 状态。接下来m行,每行有2个数x, y,表示数列的第x项可以变化成y这个值。1 \u0026lt;\u003d x \u0026lt;\u003d n。所有数字均为正整数\n\u003c/div\u003e \n\u003cdiv\u003e\n ,且小于等于100,000\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\u0026nbsp;\u003cspan style\u003d\"font-family: gbsnu8f; font-size: 9pt;\"\u003e输\u003cspan style\u003d\"font-family: gbsnu51; font-size: 9pt;\"\u003e出\u003cspan style\u003d\"font-family: gbsnu4e; font-size: 9pt;\"\u003e一个\u003cspan style\u003d\"font-family: gbsnu65; font-size: 9pt;\"\u003e整数\u003cspan style\u003d\"font-family: gbsnuff; font-size: 9pt;\"\u003e,\u003cspan style\u003d\"font-family: gbsnu88; font-size: 9pt;\"\u003e表\u003cspan style\u003d\"font-family: gbsnu79; font-size: 9pt;\"\u003e示\u003cspan style\u003d\"font-family: gbsnu5b; font-size: 9pt;\"\u003e对\u003cspan style\u003d\"font-family: gbsnu5e; font-size: 9pt;\"\u003e应\u003cspan style\u003d\"font-family: gbsnu76; font-size: 9pt;\"\u003e的\u003cspan style\u003d\"font-family: gbsnu7b; font-size: 9pt;\"\u003e答\u003cspan style\u003d\"font-family: gbsnu68; font-size: 9pt;\"\u003e案\u003cbr style\u003d\"orphans: 2; text-align: -webkit-auto; widows: 2;\"\u003e \u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e3 4\r\n1 2 3\r\n1 2\r\n2 3\r\n2 1\r\n3 4\u003c/span\u003e\u003c/div\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cspan class\u003dsampledata\u003e3\u003c/span\u003e\u003c/div\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e\u003c/p\u003e"}}]}