30721번 - Обмены в перестановке 다국어

문제

Дана перестановка $a$ чисел от 1ドル$ до $n,ドル а также набор из $m$ пар индексов. За один ход разрешается выбрать одну из этих $m$ пар и поменять элементы на соответствующих позициях местами (перестановка, соответственно, изменится). Вы можете сделать произвольное количество ходов (в частности, разрешается не делать ни одного хода).

Определим возрастающую подпоследовательность длины $k$ как набор индексов $j_1, j_2, \ldots, j_k,ドル для которых выполняются два условия:

• 1ドル \le j_1 < j_2 < \ldots < j_k \le n$;
• $a_{j_1} < a_{j_2} < \ldots < a_{j_k}$.

Какой максимально возможной длины наибольшей возрастающей подпоследовательности можно достичь при правильных обменах элементов?

입력

В первой строке заданы два числа $n$ и $m$ (1ドル \le n \le 10^4, 0 \le m \le \min(10^5, \frac{n \cdot (n - 1)}{2}$) --- длина перестановки и количество пар позиций, которые можно обменивать между собой.

В следующей строке через пробел заданы $n$ различных целых чисел $a_i$ (1ドル \le a_i \le n$) --- элементы перестановки.

Каждая из следующих $m$ строк содержит по два числа $u_i$ и $v_i$ (1ドル \le u_i, v_i \le n, u_i \neq v_i$) --- индексы позиций, элементы на которых можно менять. Гарантируется, что ни одна пара не встречается дважды.

출력

Выведите одно целое число --- максимально возможную длину наибольшей возрастающей подпоследовательности перестановки после обменов.

제한

노트

Рассмотрим перестановку из первого примера.

$[5, 2, 4, 6, 3, 1]$

Поменяем местами элементы на позициях 5ドル$ и 6ドル$.

$[5, 2, 4, 6, 1, 3]$.

Теперь поменяем местами элементы на позициях 1ドル$ и 5ドル$.

$[1, 2, 4, 6, 5, 3]$.

Длина наибольшей возрастающей подпоследовательности в такой перестановке равняется 4ドル$.

Соответствующая подпоследовательность: $[1, 2, 4, 6, 5, 3]$.