#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,st[200002],sz=0;;
vector<int>C(N),R(N),go(N),rev(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]]);
sz=0;
for(int i=0;i<N;i++)
{
go[C[i]]=i;
rev[i]=C[i];
if(go[C[i]]!=C[i])
{
st[sz++]=C[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]]);
while(sz>0 && go[st[sz-1]]==st[sz-1])sz--;
if(sz>0)
{
int ch=st[sz-1];
int j=rev[ch];
sz--;
swap(C[R[j]],C[R[ch]]);
swap(R[j],R[ch]);
swap(rev[go[j]],rev[go[ch]]);
swap(go[j],go[ch]);
}
}
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]]);
sz=0;
for(int i=0;i<N;i++)
{
go[C[i]]=i;
rev[i]=C[i];
if(go[C[i]]!=C[i])st[sz++]=C[i];
}
for(int i=0;i<N;i++)
{
C[i]=S[i];
R[S[i]]=i;
}
for(int i=0;i<q;i++)
{
swap(R[C[X[i]]],R[C[Y[i]]]);
swap(C[X[i]],C[Y[i]]);
while(sz>0 && go[st[sz-1]]==st[sz-1])sz--;
if(sz>0)
{
int ch=st[sz-1];
int j=rev[ch];
sz--;
swap(C[R[j]],C[R[ch]]);
swap(R[j],R[ch]);
P[i]=R[j],Q[i]=R[ch];
swap(rev[go[j]],rev[go[ch]]);
swap(go[j],go[ch]);
}
else P[i]=Q[i]=0;
}
return q;
}
