#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int mas[200005],pos[200005],n,a[200005],m,b[200005],c[200005],otg1[200005],otg2[200005];
bool check(int p)
{
for(int i=1;i<=n;i++)
{
mas[i]=a[i];
pos[mas[i]]=i;
}
for(int i=1;i<=p;i++)
{
swap(mas[b[i]],mas[c[i]]);
swap(pos[mas[b[i]]],pos[mas[c[i]]]);
}
int br=0;
for(int i=1;i<=n;i++)
{
if(mas[i]==i)continue;
br++;
otg1[br]=mas[i];
otg2[br]=i;
swap(pos[mas[i]],pos[i]);
swap(mas[pos[mas[i]]],mas[i]);
}
if(br<=p)return true;
return false;
}
bool p0()
{
int br=0;
for(int i=1;i<=n;i++)
{
if(a[i]==i)br++;
}
if(br==n)return true;
return false;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
n=N;
m=M;
for(int i=1;i<=n;i++)
{
a[i]=S[i-1]+1;
}
for(int i=1;i<=m;i++)
{
b[i]=X[i-1]+1;
c[i]=Y[i-1]+1;
}
if(p0())return 0;
int l=1,r=m,mid;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid))r=mid-1;
else l=mid+1;
}
for(int i=1;i<=n;i++)pos[a[i]]=i;
for(int i=1;i<=l;i++)
{
swap(a[b[i]],a[c[i]]);
swap(pos[a[b[i]]],pos[a[c[i]]]);
if(i==l&&p0())
{
P[i-1]=0;
Q[i-1]=0;
}
else
{
swap(pos[otg1[i]],pos[otg2[i]]);
swap(a[pos[otg1[i]]],a[pos[otg2[i]]]);
P[i-1]=pos[otg1[i]]-1;
Q[i-1]=pos[otg2[i]]-1;
}
}
return l;
}
