#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int p=-1,q=M,h;
vector<int>C(N),R(N),go(N);
while(p!=q-1)
{
h=(p+q)/2;
for(int i=0;i<N;i++)C[i]=S[i];
for(int i=0;i<h;i++)swap(C[X[i]],C[Y[i]]);
for(int i=0;i<N;i++)go[C[i]]=i;
for(int i=0;i<N;i++)
{
C[i]=S[i];
R[S[i]]=i;
}
for(int i=0;i<h;i++)
{
swap(R[C[X[i]]],R[C[Y[i]]]);
swap(C[X[i]],C[Y[i]]);
int ch=-1;
for(int j=0;j<N;j++)
{
if(go[j]!=j)
{
ch=j;
break;
}
}
if(ch>=0)
{
for(int j=0;j<N;j++)
{
if(go[j]==ch)
{
swap(C[R[j]],C[R[ch]]);
swap(R[j],R[ch]);
swap(go[j],go[ch]);
break;
}
}
}
}
int s=0;
for(int i=0;i<N;i++)if(go[i]==i)s++;
if(s==N)q=h;
else p=h;
}
for(int i=0;i<N;i++)C[i]=S[i];
for(int i=0;i<q;i++)swap(C[X[i]],C[Y[i]]);
for(int i=0;i<N;i++)go[C[i]]=i;
for(int i=0;i<N;i++)
{
C[i]=S[i];
R[S[i]]=i;
}
for(int i=0;i<q;i++)
{
R[C[X[i]]]=Y[i];
R[C[Y[i]]]=X[i];
swap(C[X[i]],C[Y[i]]);
int ch=-1;
for(int j=0;j<N;j++)
{
if(go[j]!=j)
{
ch=j;
break;
}
}
if(ch>=0)
{
for(int j=0;j<N;j++)
{
if(go[j]==ch)
{
swap(C[R[j]],C[R[ch]]);
P[i]=R[j];
Q[i]=R[ch];
swap(R[j],R[ch]);
swap(go[j],go[ch]);
break;
}
}
}
else P[i]=Q[i]=0;
}
return q;
}
