#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 2e5+5;
int b[MXN], whb[MXN], p[MXN], a[MXN], wh[MXN];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
if(N==1) return 0;
auto check = [&](int lim) -> bool {
iota(whb, whb+N, 0);
for(int i=0; i<lim; i++)
swap(whb[X[i]], whb[Y[i]]);
for(int i=0; i<N; i++)
p[whb[i]] = i;
iota(whb, whb+N, 0);
iota(b, b+N, 0);
for(int i=0; i<N; i++)
wh[a[i] = S[i]] = i;
int ptr=0;
for(int i=0, j; i<N; i++)
if(a[i]!=p[i]) {
swap(b[whb[X[ptr]]], b[whb[Y[ptr]]]);
swap(whb[X[ptr]], whb[Y[ptr]]);
j = wh[p[i]];
P[ptr] = b[i];
Q[ptr] = b[j];
ptr++;
swap(a[i], a[j]);
swap(wh[a[i]], wh[a[j]]);
}
if(ptr>lim) return 0;
for(int i=ptr; i<lim; i++) P[i] = Q[i] = 0;
return ptr<=lim;
};
int l=-1, r=N-1, mid;
while(r-l>1) {
mid = ((l+r)>>1);
(check(mid) ? r : l) = mid;
}
check(r);
return r;
}
