#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> nose;
vector <int> nose2;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
int l=0, r=M-1;
bool xddd=1;
vector <pair <int, int> > mbs;
for(int i=0; i<N; ++i){
if(S[i]!=i){
xddd=0;
break;
}
}
if(xddd){
return 0;
}
cerr<<"0 9\n";
while(l<r){
cerr<<(l+r)/2<<"\n";
vector <int> aux;
aux.resize(N);
for(int i=0; i<N; ++i){
aux[i]=S[i];
}
mbs.resize(0);
for(int i=0; i<=(l+r)/2; ++i){
int aguss=aux[X[i]];
aux[X[i]]=aux[Y[i]];
aux[Y[i]]=aguss;
}
int re=0;
for(int i=0; i<N; ++i){
if(aux[i]!=i){
--re;
int j=i;
while(aux[j]!=j){
int aguss=j;
j=aux[j];
cerr<<" "<<aguss<<" "<<j<<"\n";
mbs.push_back(make_pair(aguss, j));
aux[aguss]=aguss;
++re;
}
}
}
if(re<=(l+r)/2){
r=(l+r)/2;
}
else{
l=(l+r+1)/2;
}
cerr<<l<<" "<<r<<"\n";
}
vector <int> t;
t.resize(N);
for(int i=0; i<N; ++i){
t[i]=i;
}
vector <pair <int, int> > bs;
for(int i=0; i<l; ++i){
bs.push_back(make_pair(t[mbs[i].first], t[mbs[i].second]));
int aguss=t[X[l-1-i]];
t[X[l-1-i]]=t[Y[l-1-i]];
t[Y[l-1-i]]=aguss;
}
nose.resize(l);
nose2.resize(l);
for(int i=0; i<l; ++i){
P[i]=bs[l-1-i].first;
Q[i]=bs[l-1-i].second;
nose[i]=bs[l-1-i].first;
nose2[i]=bs[l-1-i].second;
}
return l;
}
