#include<bits/stdc++.h>
#include "sorting.h"
using namespace std;
const int MAX_SWAP=1000*1000;
int nbVal,nbSwap,posModif;
int autreSwap[MAX_SWAP][2];
int val[MAX_SWAP];
int obj[MAX_SWAP];
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];
}
for (int i=0;i<nbVal;i++) {
obj[i]=i;
}
for (int i=nbSwap;i>=0;i--) {
swap(obj[autreSwap[i][0]],obj[autreSwap[i][1]]);
/*for (int j=0;j<nbVal;j++) {
cout<<obj[j]<<" ";
}
cout<<endl;*/
}
for (int i=0;i<nbSwap;i++) {
swap(obj[autreSwap[i][0]],obj[autreSwap[i][1]]);
swap(val[autreSwap[i][0]],val[autreSwap[i][1]]);
posModif=0;
for (int j=0;j<nbVal;j++) {
if (val[j]!=obj[j]) {
posModif=j;
}
}
/*for (int j=0;j<nbVal;j++) {
cout<<val[j]<<" ";
}
cout<<" ";
for (int j=0;j<nbVal;j++) {
cout<<obj[j]<<" ";
}
cout<<" ";
cout<<posModif<<" : ";*/
rep.push_back({posModif,obj[val[posModif]]});
swap(val[rep.back().first],val[rep.back().second]);
/*for (int j=0;j<nbVal;j++) {
cout<<val[j]<<" ";
}
cout<<" ";
for (int j=0;j<nbVal;j++) {
cout<<obj[j]<<" ";
}
cout<<endl;*/
}
for (int i=0;i<nbSwap;i++) {
P[i]=rep[i].first;
Q[i]=rep[i].second;
}
return nbSwap;
}
