#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int findSwapPairs(int n, int *s, int m, int *x, int *y, int *p, int *q) {
vector<int> a(n), pos(n);
vector<array<int, 2>> ops(m);
auto count = [&](int k) {
for (int i = 0; i < n; ++i) {
a[i] = s[i];
}
for (int i = 0; i < k; ++i) {
swap(a[x[i]], a[y[i]]);
}
for (int i = 0; i < n; ++i) {
pos[a[i]] = i;
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (i == a[i]) {
continue;
}
int j = pos[i];
ops[cnt++] = {a[i], a[j]};
swap(pos[a[i]], pos[a[j]]);
swap(a[i], a[j]);
}
return cnt;
};
int l = 0, r = m, k = m;
while (l <= r) {
int md = (l + r) / 2;
if (count(md) <= md) {
k = md;
r = md - 1;
} else {
l = md + 1;
}
}
auto cnt = count(k);
for (int i = cnt; i < k; ++i) {
ops[i] = {0, 0};
}
for (int i = 0; i < n; ++i) {
pos[s[i]] = i;
}
auto swp = [&](int i, int j) {
swap(pos[s[i]], pos[s[j]]);
swap(s[i], s[j]);
};
for (int i = 0; i < k; ++i) {
swp(x[i], y[i]);
auto [x, y] = ops[i];
tie(p[i], q[i]) = tie(pos[x], pos[y]);
swp(p[i], q[i]);
}
return k;
}
