#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int ans = M;
int l = 0, r = M;
vi a(n), f(n);
vi b(n), p(n);
while (l <= r) {
int m = (l+r)/2;
for (int i = 0; i < n; i++) a[i] = b[i] = S[i], f[a[i]] = p[b[i]] = i;
for (int i = 0; i < m; i++) {
swap(a[X[i]], a[Y[i]]);
f[a[X[i]]] = X[i];
f[a[Y[i]]] = Y[i];
}
int moves = 0;
vi seen(n);
vvi comps;
for (int i = 0; i < n; i++) if (a[i] != i && !seen[i]) {
comps.push_back({});
int j = i;
int cnt = 0;
while (!seen[j]) {
seen[j] = 1;
comps.back().push_back(a[j]);
j = a[j];
cnt++;
}
moves += cnt-1;
}
bool ok = moves <= m;
if (!ok) {
l = m+1;
continue;
}
//cout << "S: "; for (int j = 0; j < n; j++) cout << b[j] << " "; cout << endl;
for (int i = 0; i < m; i++) {
swap(b[X[i]], b[Y[i]]);
p[b[X[i]]] = X[i];
p[b[Y[i]]] = Y[i];
//cout << "E(" << X[i] << " " << Y[i] << "): "; for (int j = 0; j < n; j++) cout << b[j] << " "; cout << endl;
if (comps.size() && comps.back().size() == 1) comps.pop_back();
if (!comps.size()) {
P[i] = Q[i] = 0;
continue;
}
int x = comps.back().back(); comps.back().pop_back();
int y = a[x];
P[i] = p[x];
Q[i] = p[y];
swap(b[p[x]], b[p[y]]);
swap(a[f[x]], a[f[y]]);
swap(f[x], f[y]);
p[b[p[x]]] = p[x];
p[b[p[y]]] = p[y];
//cout << "A(" << P[i] << " " << Q[i] << "): "; for (int j = 0; j < n; j++) cout << b[j] << " "; cout << endl;
}
ans = m;
r = m-1;
//cout << "Ok: " << ans << endl;
}
//cout << ans << endl;
//for (int i = 0; i < ans; i++) cout << P[i] << " " << Q[i] << endl;
return ans;
}
