#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
int n, m;
int *s, *x, *y, *p, *q;
int tmp[N], tmp2[N], where[N];
bool used[N];
int timer = 0;
int dfs(int u){
used[u] = true;
int cnt = 1;
if(!used[ tmp[u] ]){
cnt += dfs(tmp[u]);
}
return cnt;
}
void make_swap(int l, int r){
swap(tmp2[l], tmp2[r]);
swap(where[ tmp2[l] ], where[ tmp2[r] ]);
}
void dfs_ans (int u){
//cout << "dfs_ans " << u << endl;
//cout << tmp[u] << endl;
used[u] = true;
if(!used[ tmp[u] ]){
dfs_ans(tmp[u]);
make_swap(x[timer], y[timer]);
p[timer] = where[ tmp[u] ];
q[timer] = where[ tmp[tmp[u]] ];
swap(tmp[u], tmp[tmp[u]]);
//cout << "swap " << tmp[u] << " " << tmp[tmp[u]] << endl;
make_swap(p[timer], q[timer]);
++timer;
}
}
bool check(int mid){
for(int i = 0; i < n; i++){
tmp[i] = s[i];
used[i] = false;
}
for(int i = 0; i < mid; i++){
swap(tmp[ x[i] ], tmp[ y[i] ]);
}
int cnt = 0;
for(int i = 0; i < n; i++){
if(!used[i]){
cnt += dfs(i) - 1;
}
}
return (cnt <= mid);
}
void find_ans(int mid){
for(int i = 0; i < n; i++){
tmp[i] = s[i];
tmp2[i] = s[i];
where[s[i]] = i;
used[i] = false;
}
for(int i = 0; i < mid; i++){
swap(tmp[ x[i] ], tmp[ y[i] ]);
//swap(where[ s[x[i]] ], where[ s[y[i]] ]);
}
int cnt = 0;
for(int i = 0; i < n; i++){
if(!used[i]){
dfs_ans(i);
}
}
while(timer < mid){
p[timer] = 0;
q[timer++] = 0;
}
}
int findSwapPairs(int _n, int _s[], int _m, int _x[], int _y[], int _p[], int _q[]){
n = _n, s = _s, m = _m, x = _x, y = _y, p = _p, q = _q;
int l = 0, r = m;
while(l != r){
int mid = (l + r) >> 1;
if(check(mid)){
r = mid;
}
else{
l = mid + 1;
}
}
find_ans(l);
return l;
}
/*int _s[N], _x[N], _y[N], _p[N], _q[N];
int main(){
cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> _s[i];
}
for(int i = 0; i < m; i++){
cin >> _x[i] >> _y[i];
}
int ans = findSwapPairs(n, _s, m, _x, _y, _p, _q);
cout << ans << "\n";
for(int i = 0; i < ans; i++){
cout << _p[i] << " " << _q[i] << "\n";
}
return 0;
}*/
/*
5 6
1 2 3 4 0
0 0
0 0
0 0
0 0
0 0
0 0
*/
