#include "sorting.h"
#include <bits/stdc++.h>
#define pb push_back
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int tag[200005],seq[200005],pl[200005];
void swp(int x,int y)
{
swap(pl[seq[x]],pl[seq[y]]),swap(seq[x],seq[y]);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
int l=0,r=M;
while(l<r)
{
int mid=(l+r)/2,flag=1;
for(int i=0;i<N;++i)
seq[i]=S[i],pl[S[i]]=i,tag[i]=0;
for(int i=0;i<mid;++i)
++tag[X[i]],++tag[Y[i]];
for(int i=0;i<mid;++i)
{
--tag[X[i]],--tag[Y[i]];
swp(X[i],Y[i]);
int untag=-1;
for(int j=0;j<N;++j)
if(seq[j]!=j&&(!~untag||tag[j]<tag[untag]))
untag=j;
if(!~untag) P[i]=Q[i]=0;
else
P[i]=untag,Q[i]=pl[untag],swp(P[i],Q[i]);
}
for(int i=0;i<N&&flag;++i)
if(seq[i]!=i) flag=0;
if(flag) r=mid;
else l=mid+1;
}
int mid=l;
for(int i=0;i<N;++i)
seq[i]=S[i],pl[S[i]]=i,tag[i]=0;
for(int i=0;i<mid;++i)
++tag[X[i]],++tag[Y[i]];
for(int i=0;i<mid;++i)
{
--tag[X[i]],--tag[Y[i]];
swp(X[i],Y[i]);
int untag=-1;
for(int j=0;j<N;++j)
if(seq[j]!=j&&(!~untag||tag[j]<tag[untag]))
untag=j;
if(!~untag) P[i]=Q[i]=0;
else
P[i]=untag,Q[i]=pl[untag],swp(P[i],Q[i]);
}
return l;
}
