#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 (S[at] != targ[at] and !vis[at]) {
vis[at] = true;
at = S[at];
}
cyc++;
}
return N - cyc <= x;
};
auto apply = [&](int x) -> void {
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 (S[at] != targ[at]) {
vis[S[at]] = true;
cerr << S[at] sp S[S[at]] << endl;
P[id] = at, Q[id] = S[at];
id++;
swap(S[at], S[S[at]]);
}
vis[at] = true;
}
};
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
//
