#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];
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<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;
}
int cur_sort=0;
for(int i=0; i<m; i++)
{
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)
{
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;
}
// cout << P[i] << " " << Q[i] << endl;
}
return m;
}
#ifdef ARTHUR_LOCAL
// int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[])
int iS[MAXN];
int iX[MAXN];
int iY[MAXN];
int iP[MAXN];
int iQ[MAXN];
int main()
{
cout << findSwapPairs(1,iS,1,iX,iY,iP,iQ) << endl;
}
#endif
