// #include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 200005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
vector<pair<ll, ll>> v[MAXN];
ll cv[MAXN], s[MAXN], x[MAXN], y[MAXN], nx[MAXN];
bool d[MAXN];
bool valid(int N, ll m){
FOR(i, 0, N - 1) cv[i] = i;
FOR(i, 1, m) swap(cv[x[i]], cv[y[i]]);
FOR(i, 0, N - 1) nx[cv[i]] = i;
ll r = 0;
FOR(i, 0, N - 1) d[i] = s[cv[i]] == i;
FOR(st, 0, N - 1) if(!d[st]){
ll lpsz = 0, i = st;
do{
d[i] = true;
i = nx[s[i]];
}while(i != st);
r += lpsz - 1;
}
return r <= m;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
FOR(i, 0, N - 1) s[i] = S[i];
FOR(i, 0, M - 1) x[i] = X[i], y[i] = Y[i];
ll lo = 0, hi = M;
while(lo < hi){
ll md = (lo + hi) / 2;
if(valid(N, md)){
hi = md;
}else{
lo = md + 1;
}
}
ll itr = 0;
FOR(i, 0, N - 1) cv[i] = i;
FOR(i, 1, lo) swap(cv[x[i]], cv[y[i]]);
FOR(i, 0, N - 1) nx[cv[i]] = i;
FOR(i, 0, N - 1) d[i] = s[cv[i]] == i;
FOR(st, 0, N - 1) if(!d[st]){
ll i = st;
do{
d[i] = true;
i = nx[s[i]];
if(i != st) P[itr] = i, Q[itr] = nx[s[i]];
itr++;
}while(i != st);
}
return lo;
}
