#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int a[200000], b[200000];
int m;
int x[600000], y[600000];
bool check(int val){
for(int i=0;i<n;i++)
b[i] = a[i];
for(int i=0;i<val;i++)
swap(b[x[i]], b[y[i]]);
int cnt = n;
for(int i=0;i<n;i++){
if (b[i] == -1) continue;
cnt--;
int index = i;
do{
int nex = b[index];
b[index] = -1;
index = nex;
}while(index != i);
}
return cnt <= val;
}
int curPos[200000];
int trace(int val,int P[], int Q[]){
for(int i=0;i<n;i++)
b[i] = a[i],
curPos[a[i]] = i;
for(int i=0;i<val;i++)
swap(b[x[i]], b[y[i]]);
int cnt = 0;
for(int i=0;i<n;i++){
if (b[i] == -1) continue;
int index = i;
for(int _=0;b[index] != -1;_++){
int nex = b[index];
if (nex == i) {b[index] = -1; break;}
//~ cout << index << ' ' << nex << endl;
swap(curPos[a[x[cnt]]], curPos[a[y[cnt]]]);
swap(a[x[cnt]], a[y[cnt]]);
//~ for(int j=0;j<n;j++) cout << a[j] << ' '; cout << endl;
P[cnt] = curPos[b[index]];
Q[cnt] = curPos[b[nex]];
swap(curPos[a[P[cnt]]], curPos[a[Q[cnt]]]);
swap(a[P[cnt]], a[Q[cnt]]);
++cnt;
//~ for(int j=0;j<n;j++) cout << a[j] << ' '; cout << endl;
b[index] = -1;
index = nex;
}
}
while(cnt < val) P[cnt] = Q[cnt] = 0, ++cnt;
return val;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N;
for(int i=0;i<n;i++)
a[i] = S[i];
m = M;
for(int i=0;i<m;i++)
x[i] = X[i],
y[i] = Y[i];
int l=-1, r=m;
while(l+1<r){
int mid = (l+r)/2;
if (check(mid)) r = mid;
else l = mid;
}
return trace(r,P,Q);
}
