#include<iostream>
#include<utility>
#include "sorting.h"
using namespace std;
int t[1000000];
int gdzie[1000000];
int teraz[1000000];
int gdzie_teraz[1000000];
pair<int,int> zmiana[1000000];
int findSwapPairs(int n,int s[],int m,int x[],int y[],int p[],int q[])
{
bool czy=0;
p[0]=0;
q[0]=1;
for(int i=0;i<n;i++)
if(s[i]!=i)
{
czy=1;
break;
}
if(czy==0)
return 0;
int pocz=0,kon=m+1,sre;
int wynik=m;
while(pocz<kon)
{
sre=(pocz+kon)/2;
//cout<<"sprawdzam "<<sre<<"\n";
for(int i=0;i<n;i++)
{
t[i]=s[i];
gdzie[s[i]]=i;
}
for(int i=0;i<sre;i++)
{
swap(t[x[i]],t[y[i]]);
swap(gdzie[t[x[i]]],gdzie[t[y[i]]]);
}
for(int i=0;i<n;i++)
{
teraz[i]=i;
gdzie_teraz[i]=i;
}
int zle=0;
for(int i=sre-1;i>=0;i--)
{
while(zle<n && gdzie_teraz[zle]==gdzie[zle])
zle++;
if(zle>=n)
break;
zmiana[i]={gdzie_teraz[zle],gdzie_teraz[t[gdzie_teraz[zle]]]};
swap(teraz[gdzie_teraz[zle]],teraz[gdzie_teraz[t[gdzie_teraz[zle]]]]);
swap(gdzie_teraz[zle],gdzie_teraz[t[gdzie_teraz[zle]]]);
swap(gdzie[t[x[i]]],gdzie[t[y[i]]]);
swap(t[x[i]],t[y[i]]);
swap(gdzie_teraz[teraz[x[i]]],gdzie_teraz[teraz[y[i]]]);
swap(teraz[x[i]],teraz[y[i]]);
}
bool ok=0;
for(int i=0;i<n;i++)
if(teraz[i]!=t[i])
ok=1;
//cout<<"ok "<<ok<<"\n";
if(ok==0)
{
wynik=sre;
kon=sre;
for(int i=0;i<sre;i++)
{
p[i]=zmiana[i].first;
q[i]=zmiana[i].second;
}
}
else pocz=sre+1;
}
return wynik;
}
