#include "sorting.h"
#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a; i<int(b); i++)
using namespace std;
vector<pair<int, int> > moves;
int movestofix(int Ii[],int Ss[], int N) {
int I[N], S[N];
rep (i,0,N) { I[i]=Ii[i];S[i]=Ss[i];}
moves.clear();
//I[i] is not value at i, but index of value i in S
int counter=0;
rep(i,0,N) {
if (S[i]==i) continue;
counter++;
int a,b;
a=i;
b=I[i];
//a och b byter plats
int sa,sb;
sa=S[a];
sb=S[b];
moves.push_back(make_pair(a,b));
S[a]=sb;
S[b]=sa;
I[sa]=b;
I[sb]=a;
}
moves.push_back(make_pair(0,0));
return counter;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int I[N];
rep (i,0,N) {
I[S[i]]=i;
}
int i=0;
int hi,lo;
hi=N;
lo=-1;
while (hi>lo+1) {
int mid=(hi+lo)/2;
int copyI[N],copyS[N];
rep (x,0,N) {
copyI[x]=I[x];
copyS[x]=S[x];
}
rep (x,0,mid) {
int a,b;
a=X[x];
b=Y[x];
//a och b byter plats
int sa,sb;
sa=copyS[a];
sb=copyS[b];
copyS[a]=sb;
copyS[b]=sa;
copyI[sa]=b;
copyI[sb]=a;
}
if (movestofix(copyI,copyS,N)>mid) lo=mid;
else hi=mid;
}
i=hi;
int mid = hi;
int copyI[N],copyS[N];
rep (x,0,N) {
copyI[x]=I[x];
copyS[x]=S[x];
}
rep (x,0,mid) {
int a,b;
a=X[x];
b=Y[x];
//a och b byter plats
int sa,sb;
sa=copyS[a];
sb=copyS[b];
copyS[a]=sb;
copyS[b]=sa;
copyI[sa]=b;
copyI[sb]=a;
}
if (movestofix(copyI,copyS,N)>mid) lo=mid;
else hi=mid;
rep (j,0,N) {S[j]=j;I[j]=j;}
for (int j=i-1;j>=0; j--) {
P[j]=S[moves[j].first];
Q[j]=S[moves[j].second];
//swap(switches[X[j]],switches[Y[j]]);
int a,b;
a=I[X[j]];
b=I[Y[j]];
//a och b byter plats
int sa,sb;
sa=S[a];
sb=S[b];
S[a]=sb;
S[b]=sa;
I[sa]=b;
I[sb]=a;
}
return i;
}
