#include<bits/stdc++.h>
#include "sorting.h"
using namespace std;
const int MAX_SWAP=1000*1000;
int nbVal,nbSwap,posModif,nouvVal,deb,fin,mid,verif;
int autreSwap[MAX_SWAP][2];
int val[MAX_SWAP];
int posDansObj[MAX_SWAP];
int obj[MAX_SWAP];
vector<pair<int,int>> nouv;
vector<pair<int,int>> rep;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
nbVal=N;
nbSwap=M;
for (int i=0;i<nbVal;i++) {
val[i]=S[i];
}
for (int i=0;i<nbSwap;i++) {
autreSwap[i][0]=X[i];
autreSwap[i][1]=Y[i];
}
fin=nbSwap;
rep.resize(nbSwap);
while (deb!=fin) {
mid=(deb+fin)/2;
nouv.clear();
for (int i=0;i<nbVal;i++) {
obj[i]=i;
posDansObj[i]=i;
}
for (int i=0;i<nbVal;i++) {
val[i]=S[i];
}
for (int i=mid-1;i>=0;i--) {
posDansObj[obj[autreSwap[i][0]]]=autreSwap[i][1];
posDansObj[obj[autreSwap[i][1]]]=autreSwap[i][0];
swap(obj[autreSwap[i][0]],obj[autreSwap[i][1]]);
}
for (int i=0;i<mid;i++) {
posDansObj[obj[autreSwap[i][0]]]=autreSwap[i][1];
posDansObj[obj[autreSwap[i][1]]]=autreSwap[i][0];
swap(obj[autreSwap[i][0]],obj[autreSwap[i][1]]);
swap(val[autreSwap[i][0]],val[autreSwap[i][1]]);
posModif=0;
nouvVal=0;
for (int j=0;j<nbVal;j++) {
if (val[j]!=obj[j]) {
posModif=j;
}
}
nouvVal=posDansObj[val[posModif]];
/*for (int j=0;j<nbVal;j++) {
if (obj[j]==val[posModif]) {
nouvVal=j;
}
}*/
nouv.push_back({posModif,nouvVal});
swap(val[posModif],val[nouvVal]);
}
verif=1;
for (int i=0;i<nbVal;i++) {
if (val[i]!=i) {
verif=0;
}
}
if (verif==0) {
deb=mid+1;
}
if (verif==1) {
fin=mid;
if (nouv.size()<rep.size()) {
rep=nouv;
}
}
}
for (int i=0;i<deb;i++) {
P[i]=rep[i].first;
Q[i]=rep[i].second;
}
return deb;
}
