#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include "sorting.h"
bool chk(int T, int N, int S[], int X[], int Y[], int P[] = nullptr, int Q[] = nullptr) {
vector<int> cur(N);
for(int i = 0; i < N; i++) cur[i] = S[i];
for(int i = 0; i < T; i++)
swap(cur[X[i]], cur[Y[i]]);
vector<pair<int, int>> need;
vector<int> pos(N);
for(int i = 0; i < N; i++) pos[cur[i]] = i;
vector<int> 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;
vector<int> realS(N), realpos(N);
for(int i = 0; i < N; i++) {
realS[i] = S[i];
realpos[S[i]] = i;
}
for(int i = 0; i < T; i++) {
int ex = X[i], ey = Y[i];
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] = pu;
realpos[v] = pv;
}
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(h - l + 1) {
int m = l + (l + h) >> 1;
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;
}
