#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
int n,m;
pair<int,int> his[200005],sol[200005];
int init[200005],ord[200005],unde[200005];
bool is_sorted()
{
for(int i=1;i<n;i++)
if(ord[i]<ord[i-1])
return 0;
return 1;
}
bool verif(int ult)
{
for(int pas=0;pas<=ult;pas++)
{
for(int i=0;i<n;i++)
ord[i] = init[i];
for(int i=0;i<=pas;i++)
swap(ord[his[i].first],ord[his[i].second]);
for(int i=0;i<pas;i++)
swap(ord[sol[i].first],ord[sol[i].second]);
for(int i=0;i<n;i++)
unde[ord[i]] = i;
for(int i=pas+1;i<=ult;i++)
swap(ord[his[i].first],ord[his[i].second]);
pair<int,int> aux = {-1,-1};
for(int i=0;i<n;i++)
{
if(ord[i]!=i)
{
aux = {ord[i],i};
break;
}
}
/*for(int i=0;i<n;i++)
cerr<<ord[i]<<" ";
cerr<<" "<<aux.first<<" "<<aux.second<<"\n";*/
if(aux.first!=-1)
{
sol[pas].first = unde[aux.first];
sol[pas].second = unde[aux.second];
}
else
sol[pas] = {0,0};
}
for(int i=0;i<n;i++)
ord[i] = init[i];
for(int pas=0;pas<=ult;pas++)
{
swap(ord[his[pas].first], ord[his[pas].second]);
swap(ord[sol[pas].first], ord[sol[pas].second]);
}
return is_sorted();
}
int findSwapPairs(int N, int copS[], int M, int X[], int Y[], int P[], int Q[])
{
n = N;
m = M;
for(int i=0;i<N;i++)
{
init[i] = copS[i];
ord[i] = init[i];
}
for(int i=0;i<M;i++)
{
his[i] = {X[i], Y[i]};
}
if(is_sorted())
return 0;
//assert(verif(M-1));
verif(M-1);
for(int i=0;i<M;i++)
{
P[i] = sol[i].first;
Q[i] = sol[i].second;
}
return M;
}
