016 - シゲソート

時間制限 1 秒 / メモリ制限 64 MB / 得点 514 / x 0 /


TLE
1sec
MLE
64MB
得点
514
出題ミスがあったらご一報ください。

問題

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

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

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

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

入力

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

出力

求める数

制約

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

テストケース

例1

入力

2 1
2
1
1 2

出力

2