#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
if (is_sorted(S, S+N)) return 0;
int id = 0;
auto check = [&](int x) -> bool {
vector<int> targ(N), inv(N);
for (int i = 0; i < N; i++) targ[i] = S[i];
for (int i = 0; i < x; i++) {
swap(targ[X[i]], targ[Y[i]]);
}
vector<bool> vis(N);
int amt = 0;
for (int i = 0; i < N; i++) {
if (vis[i]) continue;
int at = i;
vis[at] = true;
while (!vis[targ[at]]) {
vis[targ[at]] = true;
at = targ[at];
amt++;
}
}
return amt <= x;
};
auto apply = [&](int x) -> void {
vector<int> targ(N), inv(N);
for (int i = 0; i < N; i++) targ[i] = S[i];
for (int i = 0; i < x; i++) {
swap(targ[X[i]], targ[Y[i]]);
}
for (int i = 0; i < N; i++) inv[S[i]] = i;
vector<bool> vis(N, 0);
int id = 0;
for (int i = 0; i < N; i++) {
if (vis[i]) continue;
int at = i;
vis[at] = true;
while (!vis[targ[at]]) {
vis[targ[at]] = true;
swap(S[X[id]], S[Y[id]]);
inv[S[X[id]]] = X[id];
inv[S[Y[id]]] = Y[id];
P[id] = inv[targ[at]];
Q[id] = inv[targ[targ[at]]];
swap(S[P[id]], S[Q[id]]);
inv[S[P[id]]] = P[id];
inv[S[Q[id]]] = Q[id];
at = targ[at];
id++;
}
}
};
int l = 0, r = N;
while (r - l > 1) {
int m = (l + r) / 2;
if (check(m)) {
r = m;
} else {
l = m;
}
}
cerr << r << endl;
apply(r);
return r;
}
// 3 0 4 2 1
//
