#include "sorting.h"
#include <vector>
using namespace std;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int n=N;
bool donene;
vector<int> fns(n), cns(n);
for(int i=0; i<n; i++){
fns[i] = S[i];
cns[i] = S[i];
}
for(int i=0; i<N; i++){
swap(fns[X[i]], fns[Y[i]]);
}
// now we have N swaps to make until it must be sorted...
// this is more than enough :p
int target;
for(int i=0; i<n; i++){
if(1==1) // check to see if it's already sorted (how... goofy)
{
donene=true;
for(int t=1; t<n; t++){
if(cns[t-1] > cns[t]){
donene=false;
break;
}
}
if(donene)return i;
}
swap(cns[X[i]], cns[Y[i]]);
for(int _=0; _<n; _++){
// only do swaps with respect to the final layout
// we do not care about cns
// cns only exists because the question is stupid
if(fns[_]==i){
target = _;
break;
}
}
P[i] = i;
Q[i] = target;
swap(fns[P[i]], fns[Q[i]]);
swap(cns[P[i]], cns[Q[i]]);
}
return N;
}
