016 - シゲソート

出題ミスがあったらご一報ください。

問題

あなたは美香沙(みかさ)という神仁(かみひと)の弟(妹)である。
美香沙は神仁にもらった1~Nまでの整数列を持っています。
神仁は美香沙とこの数列を使ってソートアルゴリズムの勉強をしようと思います。
そのソートは次のように行います。

1. 神仁が整数列を与えます。便宜上左からa₁......a_Nとします
2. 神仁はM回数字をペアで言います。この二つの数字の組、(x_i, y_i)を倉_iと表現します
3. その後、美香沙は倉₁から倉_Mについてそれぞれ使う回数を決めます。
4. 美香沙は各倉を好きな順番で選択してa_xとa_yを入れ替えます。

3, 4の動作をなるべく i = a_i になるように最適に行ったとき、この操作はシゲソートと言います。
シゲソートしたときにi = a_iとなる数を求めてください。

3の操作で倉₁を2回、倉₂を1回使うと決めたとき、4の操作で
倉₁, 倉₁, 倉₂
倉₁, 倉₂, 倉₁
倉₂, 倉₁, 倉₁
のように選択することができます。

入力

N M
a1
......
aN
x1 y1
......
xM yM

出力

求める数

制約

$2$ ≤ $N$ ≤ $10$⁴
$1$ ≤ $M$ ≤ $10$⁶
$1$ ≤ $a$, $b$ ≤ $N$
x_i != y_i
aは1~Nの整数を並び替えた数。
どの倉も必ず1回は選択しなければいけない。

テストケース

例1

入力

2 1
2
1
1 2

出力

2