Swaps in a Permutation

You are given a permutation $a$ of the numbers from $1$ to $n$ and a set of $m$ index pairs. In one move, you may choose one of these $m$ pairs and swap the elements at those two positions, which changes the permutation. You may make any number of moves, including none.

An increasing subsequence of length $k$ is a set of indices $j_1, j_2, \ldots, j_k$ that satisfies both conditions:

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

What is the maximum possible length of the longest increasing subsequence after the swaps?

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^4$, $0 \le m \le \min(10^5, \frac{n \cdot (n - 1)}{2})$), the length of the permutation and the number of position pairs that can be swapped.

The second line contains $n$ distinct integers $a_i$ ($1 \le a_i \le n$), the elements of the permutation.

Each of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), the positions whose elements can be swapped. No pair appears more than once.

Print one integer: the maximum possible length of the longest increasing subsequence of the permutation after the swaps.

Consider the permutation from the first example, $[5, 2, 4, 6, 3, 1]$.

Swap the elements at positions $5$ and $6$: $[5, 2, 4, 6, 1, 3]$.

Now swap the elements at positions $1$ and $5$: $[1, 2, 4, 6, 5, 3]$.

The longest increasing subsequence of this permutation has length $4$. The corresponding subsequence is $[1, 2, 4, 6, 5, 3]$.