#include "sorting.h"
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int x[200005];
int y[200005];
int vec[200005];
int vec2[200005];
int bila[200005];
int fre[200005];
vector<int>ciclu;
int n;
void dfs(int poz)
{
if(fre[poz]==1)
{
return;
}
fre[poz]=1;
ciclu.push_back(poz);
dfs(bila[poz]);
}
int vmax=10000000;
set<pair<int,int> >positii[200005];
pair<int,int>getpositions(int timp,int bila1,int bila2)
{
pair<int,int> r1=*(prev(positii[bila1].upper_bound({timp,vmax})));
pair<int,int> r2=*(prev(positii[bila2].upper_bound({timp,vmax})));
swap(positii[bila1],positii[bila2]);
return make_pair(r1.second,r2.second);
}
vector<pair<int,int> > solutie(int nroper)
{
vector<pair<int,int>>oper;
for(int i=0;i<n;i++)
{
fre[i]=0;
vec2[i]=vec[i];
positii[vec2[i]].insert({0,i});
}
for(int i=0;i<nroper;i++)
{
positii[vec2[x[i]]].insert({i+1,y[i]});
positii[vec2[y[i]]].insert({i+1,x[i]});
swap(vec2[x[i]],vec2[y[i]]);
}
for(int i=0;i<n;i++)
{
bila[i]=vec2[i];
}
for(int i=0;i<n;i++)
{
if(fre[i]==0)
{
ciclu.clear();
dfs(i);
for(int j=1;j<ciclu.size();j++)
{
oper.push_back(getpositions(oper.size()+1,ciclu[j-1],ciclu[j]));
//cout<<ciclu[0]<<" "<<ciclu[j]<<'\n';
//oper.push_back({ciclu[0],ciclu[j]});
}
}
}
return oper;
}
int check(int nroper)
{
for(int i=0;i<n;i++)
{
fre[i]=0;
vec2[i]=vec[i];
}
for(int i=0;i<nroper;i++)
{
swap(vec2[x[i]],vec2[y[i]]);
}
for(int i=0;i<n;i++)
{
bila[i]=vec2[i];
}
int pasi=0;
for(int i=0;i<n;i++)
{
if(fre[i]==0)
{
ciclu.clear();
dfs(i);
pasi=pasi+ciclu.size()-1;
}
}
if(pasi<=nroper)
{
return 1;
}
return 0;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
n=N;
for(int i=0; i<N; i++)
{
vec[i]=S[i];
}
for(int i=0; i<M; i++)
{
x[i]=X[i];
y[i]=Y[i];
}
int st=0,dr=M;
while(st<=dr)
{
int mij=(st+dr)/2;
if(check(mij)==1)
{
dr=mij-1;
}
else
{
st=mij+1;
}
}
vector<pair<int,int> >rez2=solutie(dr+1);
for(int i=0;i<rez2.size();i++)
{
P[i]=rez2[i].first;
Q[i]=rez2[i].second;
}
return rez2.size();
}
