#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
#include "sorting.h"
#endif
using namespace std;
const int MAXN = 500;
int eend[MAXN];
int eend_inv[MAXN];
// int blank_slate[MAXN];
void eend_swap(int a, int b)
{
int one = eend[a];
int two = eend[b];
eend[a]=two;
eend[b]=one;
}
void eend_inv_swap(int a, int b)
{
int one = eend_inv[a];
int two = eend_inv[b];
eend_inv[a]=two;
eend_inv[b]=one;
}
int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[])
{
// for(int i=0; i<MAXN; i++) blank_slate[i]=i;
for(int i=0; i<n; i++)
{
eend[i]=i;
}
for(int i=0; i<m; i++)
{
eend_swap(X[i],Y[i]);
}
for(int i=0; i<n; i++)
{
eend_inv[eend[i]]=i;
}
// for(int i=0; i<n; i++)
// {
// cout << i << " " << eend[i] << endl;
// }
int cur_sort=0;
for(int i=0; i<m; i++)
{
// for(int i=0; i<5; i++)
// {
// cout << S[i] << " ";
// }
// cout << endl;
// for(int i=0; i<5; i++)
// {
// cout << eend_inv[i] << " ";
// }
//cout << endl;
eend_inv_swap(X[i],Y[i]); // correct ???
int one = S[X[i]];
int two = S[Y[i]];
S[X[i]]=two;
S[Y[i]]=one;
bool upd=0;
while(cur_sort < n)
{
int pos_s=-1;
int pos_e=-1;
for(int j=0; j<n; j++)
{
if(S[j]==cur_sort) pos_s=j;
if(eend_inv[j]==cur_sort) pos_e=j;
}
if(pos_e == pos_s && pos_e != -1)
{
// cout << cur_sort << " is sorted bro" << endl;
cur_sort++;
continue;
}
one = S[pos_s];
two = S[pos_e];
S[pos_s]=two;
S[pos_e]=one;
P[i]=pos_s;
Q[i]=pos_e;
upd=1;
cur_sort++;
break;
}
if(!upd)
{
P[i]=0;
Q[i]=0;
//return i+1;
}
// cout << P[i] << " " << Q[i] << endl;
}
//cout << "done" << endl;
return m;
}
