#include <bits/stdc++.h>
using namespace std;
#include "sorting.h"
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
int low = 0, high = M, a[N], g[N];
function<int(int)> find = [&](int v){
bitset<1<<18> vis;
for(int i=0; i<N; ++i){
g[S[i]] = i;
a[i] = S[i];
P[i] = Q[i] = 0;
}
for(int i=0; i<v; ++i) swap(g[a[X[i]]], g[a[Y[i]]]), swap(a[X[i]], a[Y[i]]);
vector<array<int, 2>> t;
function<void(int)> dfs = [&](int u){
vis[u] = 1;
if(!vis[g[u]]) t.push_back({u, g[u]}), dfs(g[u]);
};
for(int i=0; i<N; ++i){
if(!vis[g[S[i]]]) dfs(g[S[i]]);
g[S[i]] = i, a[i] = S[i];
}
for(int i=0; i<min(v, (int)t.size()); ++i){
swap(g[a[X[i]]], g[a[Y[i]]]);
swap(a[X[i]], a[Y[i]]);
P[i] = g[t[i][0]], Q[i] = g[t[i][1]];
}
return t.size();
};
while(low < high){
int v = (low + high) / 2;
if(find(v) <= v) high = v;
else low = v + 1;
}
find(low);
return low;
}
