#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include "sorting.h"
vector<int> cur, pos, tmp, realS, realpos;
bool chk(int T, int N, int S[], int X[], int Y[], int P[] = nullptr, int Q[] = nullptr) {
cur.assign(S, S + N);
for(int i = 0; i < T; i++)
swap(cur[X[i]], cur[Y[i]]);
pos.resize(N);
for(int i = 0; i < N; i++) pos[cur[i]] = i;
vector<pair<int, int>> need;
tmp = cur;
for(int i = 0; i < N; i++) {
if(tmp[i] != i) {
int v1 = tmp[i];
int v2 = i;
int p2 = pos[i];
need.push_back({v1, v2});
swap(tmp[i], tmp[p2]);
pos[v1] = p2;
pos[v2] = i;
}
}
if(need.size() > T) return false;
if(P == nullptr) return true;
realS.assign(S, S + N);
realpos.resize(N);
for(int i = 0; i < N; i++) realpos[realS[i]] = i;
for(int i = 0; i < T; i++) {
int ex = X[i], ey = Y[i];
if(ex != ey) {
int evx = realpos[ex], evy = realpos[ey];
swap(realS[ex], realS[ey]);
realpos[evx] = ex;
realpos[evy] = ey;
}
if(i < need.size()) {
auto [u, v] = need[i];
int pu = realpos[u];
int pv = realpos[v];
P[i] = pu;
Q[i] = pv;
swap(realS[pu], realS[pv]);
realpos[u] = pv;
realpos[v] = pu;
}
else P[i] = Q[i] = 0;
}
return true;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int l = 0, h = M, R = M;
while(l <= h) {
int m = l + (h - l) / 2;
if(chk(m, N, S, X, Y)) {
R = m;
h = m - 1;
}
else l = m + 1;
}
chk(R, N, S, X, Y, P, Q);
return R;
}
