题目描述

$1$ から $N$ までの整数を並び替えた順列 $p_1$, $p_2$, .., $p_N$ があります。 また、 $1$ 以上 $N$ 以下の整数のペアが $M$ 個与えられます。 これらは $(x_1,y_1)$, $(x_2,y_2)$, .., $(x_M,y_M)$ で表されます。 シカの AtCoDeer くんは順列 $p$ に次の操作を好きなだけ行って、 $p_i\ =\ i$ となる $i$ ($1$ $<\ =$ $i$ $<\ =$ $N$) の数を最大にしようと考えています。

• $1$ $<\ =$ $j$ $<\ =$ $M$ なる $j$ を選び、 $p_{x_j}$ と $p_{y_j}$ をスワップする

操作後の $p_i\ =\ i$ となる $i$ の数として考えうる最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $p_1$ $p_2$ $..$ $p_N$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_M$ $y_M$

输出格式

操作後の $p_i\ =\ i$ となる $i$ ($1$ $<\ =$ $i$ $<\ =$ $N$) の数として考えうる最大値を出力せよ。

题目大意

给一个 $1$ 到 $N$ 的整数排列：$p_1,p_2,\ldots,p_N$.

再给出 $M$ 对整数对 $(x_1,y_1),(x_2,y_2),\ldots (x_M,y_M)$ ，其中 $\forall i ,1\leqslant x_i,y_i\leqslant N$.

每对整数对对应一个操作，第 $i$ 对整数对对应着操作：将排列中第 $x_i$ 个数和第 $y_i$ 个数交换。

现在 AtCoDeer 希望通过执行任意次交换操作，使得 $p_i=i$ 的数量尽可能多。求出按任意顺序执行任意次操作后，最多能使多少 $p_i=i$.

5 2
5 3 1 4 2
1 3
5 4

2

3 2
3 2 1
1 2
2 3

3

10 8
5 3 6 8 7 10 9 1 2 4
3 1
4 1
5 9
2 5
6 5
3 5
8 9
7 9

8

5 1
1 2 3 4 5
1 5

5

提示

制約

• $2$ $<\ =$ $N$ $<\ =$ $10^5$
• $1$ $<\ =$ $M$ $<\ =$ $10^5$
• $p$ は $1$ から $N$ までの整数を並び替えた順列
• $1$ $<\ =$ $x_j,y_j$ $<\ =$ $N$
• $x_j$ $≠$ $y_j$
• $i$ $≠$ $j$ なら、 $\{x_i,y_i\}$ $≠$ $\{x_j,y_j\}$
• 入力は全て整数

Sample Explanation 1

$j=1$ を選んで操作すると、 $p$ は 1 3 5 4 2 となり、これがベストなので答えは $2$ です。

Sample Explanation 2

例えば $j=1$, $j=2$, $j=1$ の順に操作すると、 $p$ は 1 2 3 となり明らかにこれがベストです。 同じ $j$ を何回選んでもいいことに注意してください。

Sample Explanation 4

操作をする必要はありません。