配点 : $400$ 点

問題文

$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$ $\leq$ $i$ $\leq$ $N$) の数を最大にしようと考えています。

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

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

制約

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

入力

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

$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$ $\leq$ $i$ $\leq$ $N$) の数として考えうる最大値を出力せよ。

5 2
5 3 1 4 2
1 3
5 4

2

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

3 2
3 2 1
1 2
2 3

3

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

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

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