#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);
iota(targ.begin(), targ.end(), 0);
for (int i = 0; i < x; i++) {
swap(targ[X[i]], targ[Y[i]]);
}
vector<bool> vis(N);
int cyc = 0;
for (int i = 0; i < N; i++) {
if (vis[i]) continue;
int at = i;
while (!vis[at]) {
vis[at] = true;
at = S[at];
}
cyc++;
}
return N - cyc <= x;
};
auto apply = [&](int x) -> void {
vector<int> A(N);
for (int i = 0; i < N; i++) A[i] = S[i];
for (int i = 0; i < x; i++) {
swap(A[X[i]], A[Y[i]]);
}
vector<bool> vis(N, 0);
for (int i = 0; i < N; i++) {
if (vis[i]) continue;
vector<int> cyc;
int at = i;
while (!vis[at]) {
vis[at] = true;
cyc.push_back(at);
at = A[at];
}
for(int j = 1; j < cyc.size(); j++) {
P[id] = cyc[0], Q[id] = cyc[j];
id++;
swap(A[cyc[0]], A[cyc[j]]);
}
}
};
int l = 0, r = N;
while (r - l > 1) {
int m = (l + r) / 2;
if (check(m)) {
r = m;
} else {
l = m;
}
}
apply(r);
return r;
}
// 3 0 4 2 1
//
