#include"sorting.h"
#include<bits/stdc++.h>
using namespace std;
int findSwapPairs(int n,int S[],int m,int X[],int Y[],int P[],int Q[])
{
int l=0,r=m,ans=0;
while(l<=r)
{
int mid=(l+r)/2;
vector<int> p(n),q(n);
for(int i=0;i<n;i++) p[i]=i;
for(int i=mid-1;i+1;i--) swap(p[X[i]],p[Y[i]]);
for(int i=0;i<n;i++) q[p[i]]=i;
for(int i=0;i<n;i++) p[i]=q[S[i]];
for(int i=0;i<n;i++) q[p[i]]=i;
int cnt=0;
for(int i=0;i<n;i++)
{
int x=i,y=q[i];
if(x!=y) cnt++,swap(p[x],p[y]),swap(q[p[x]],q[p[y]]);
}
if(cnt<=mid) r=mid-1,ans=mid;
else l=mid+1;
}
vector<int> p(n),q(n);
for(int i=0;i<n;i++) p[i]=i;
for(int i=ans-1;i+1;i--) swap(p[X[i]],p[Y[i]]);
for(int i=0;i<n;i++) q[p[i]]=i;
for(int i=0;i<n;i++) p[i]=q[S[i]];
for(int i=0;i<n;i++) q[p[i]]=i;
int cnt=0;
for(int i=0;i<n;i++)
{
int x=i,y=q[i];
if(x!=y) P[cnt]=x,Q[cnt]=y,cnt++,swap(p[x],p[y]),swap(q[p[x]],q[p[y]]);
}
while(cnt<ans) P[cnt]=Q[cnt]=0,cnt++;
for(int i=0;i<n;i++) p[i]=q[i]=i;
for(int i=0;i<ans;i++)
{
int l=q[X[i]],r=q[Y[i]];
swap(p[l],p[r]);
swap(q[p[l]],q[p[r]]);
P[i]=p[P[i]],Q[i]=p[Q[i]];
}
return ans;
}
