#include "sorting.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int N=2e3+100;
int p[N],ind[N];
bool vis[N];
int findSwapPairs(int n, int s[], int m, int x[], int y[], int P[], int Q[]) {
if(is_sorted(s,s+n))
return 0;
for(int i=0;i<n;i++)vis[i]=0,p[i]=s[i];
for(int use=0;use<m;use++)
{
swap(p[x[use]],p[y[use]]);
for(int i=0;i<n;i++)vis[i]=0;
vector<pair<int,int>> req;
for(int i=0;i<n;i++)
{
if(vis[i])continue;
int j=i;
vector<int> cyc;
while(!vis[j])
{
cyc.push_back(j);
vis[j]=1;
j=p[j];
}
for(int i=1;i<cyc.size();i++)
{
req.push_back({p[cyc[i-1]],p[cyc[i]]});
}
// cout<<"Cycle ";
// for(auto x:cyc)cout<<x<<' ';
// cout<<endl;
}
if(req.size()>(use+1))
{
continue;
}
for(int i=0;i<n;i++)p[i]=s[i],ind[s[i]]=i;
for(int i=0;i<m;i++)P[i]=0,Q[i]=0;
// if(req.size()>m)
// {
// return 0;
// }
for(int i=0;i<req.size();i++)
{
swap(ind[p[x[i]]],ind[p[y[i]]]);
swap(p[x[i]],p[y[i]]);
P[i]=ind[req[i].first],Q[i]=ind[req[i].second];
swap(ind[p[P[i]]],ind[p[Q[i]]]);
swap(p[P[i]],p[Q[i]]);
if(is_sorted(p,p+n))
return i+1;
// swap()
}
for(int i=req.size();i<=use;i++)
{
swap(ind[p[x[i]]],ind[p[y[i]]]);
swap(p[x[i]],p[y[i]]);
if(is_sorted(p,p+n))
return i+1;
}
return use+1;
}
return m;
}
