#include<bits/stdc++.h>
#include "sorting.h"
using namespace std;
int n,m,cur[600005],def[600005],x[600005],y[600005];
int p[600005],q[600005],where[600005],cnt,ans;
void Swap(int A,int B) {
int tmp;
tmp=where[cur[A]];
where[cur[A]]=where[cur[B]];
where[cur[B]]=tmp;
tmp=cur[A];
cur[A]=cur[B];
cur[B]=tmp;
}
int param(int s,int e) {
int piv=(s+e)/2,i;
for(i=0;i<n;i++) {
cur[i]=def[i];
where[cur[i]]=i;
}
for(i=0;i<piv;i++) {
Swap(x[i],y[i]);
}
cnt=0;
for(i=0;i<n;i++) {
while(cur[i]!=i) {
p[cnt]=cur[i];
q[cnt]=cur[cur[i]];
Swap(i,cur[i]);
cnt++;
}
}
if(s==e)return s;
if(cnt<=piv) return param(s,piv);
return param(piv+1,e);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int i; n=N; m=M;
for(i=0;i<n;i++) def[i]=S[i];
for(i=0;i<m;i++) {
x[i]=X[i];
y[i]=Y[i];
}
ans=param(0,m);
for(i=0;i<n;i++) {
cur[i]=def[i];
where[cur[i]]=i;
}
for(i=0;i<cnt;i++) {
Swap(x[i],y[i]);
P[i]=where[p[i]]; Q[i]=where[q[i]];
Swap(where[p[i]],where[q[i]]);
}
for(i=cnt;i<ans;i++) {P[i]=0;Q[i]=0;}
return ans;
}
