#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;
int i;
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<M; 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 c=0; c<3*n; c++){
i = c%n;
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 c;
}
swap(cns[X[c]], cns[Y[c]]);
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[c] = i;
Q[c] = target;
swap(fns[P[c]], fns[Q[c]]);
swap(cns[P[c]], cns[Q[c]]);
}
return 3*n;
}
