#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
int tab[200005],pos[200005],L;
ii ans[200005];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int l=0,r=M;
while(l<=r){
for (int i = 0; i < N; ++i){
tab[i]=S[i];
pos[S[i]]=i;
}
int med=(l+r)>>1,idx=0;
for (int i = 0; i < med; ++i)
swap(pos[tab[X[i]]],pos[tab[Y[i]]]),swap(tab[X[i]],tab[Y[i]]);
for (int i = 0; i < N; ++i)
{
if(tab[i]!=i){
int k=pos[i];
ans[idx++]={i,tab[i]};
swap(pos[tab[i]],pos[i]);
swap(tab[i],tab[k]);
}
}
if(idx>med)l=med+1;
else{
L=med;
for (int i = 0; i < N; ++i){
tab[i]=S[i];
pos[S[i]]=i;
}
for (int i = 0; i < med; ++i)
{
swap(pos[tab[X[i]]],pos[tab[Y[i]]]),swap(tab[X[i]],tab[Y[i]]);
if(i<idx)P[i]=pos[ans[i].fi],Q[i]=pos[ans[i].se],swap(tab[P[i]],tab[Q[i]]),swap(pos[ans[i].fi],pos[ans[i].se]);
else P[i]=Q[i]=0;
}
r=med-1;
}
}
return L;
}
