#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
vector<pair<int, int>> res;
function<bool(int)> check = [&](int len) -> bool {
vector<int> s(n), pos(n);
for (int i = 0; i < n; i++) {
s[i] = S[i];
pos[S[i]] = i;
}
res.resize(len);
vector<int> p(n), q(n);
iota(p.begin(), p.end(), 0);
iota(q.begin(), q.end(), 0);
auto do_swap = [&](int i, int j) {
swap(p[i], p[j]);
swap(q[p[i]], q[p[j]]);
};
for (int i = len - 1; i >= 0; i--) {
do_swap(X[i], Y[i]);
}
int l = n - 1;
for (int i = 0; i < len; i++) {
do_swap(X[i], Y[i]);
swap(s[X[i]], s[Y[i]]);
swap(pos[s[X[i]]], pos[s[Y[i]]]);
while (l >= 0 && q[l] == pos[l])
l--;
if (l == -1)
res[i] = {0, 0};
else {
res[i] = {pos[l], q[l]};
}
swap(s[res[i].first], s[res[i].second]);
swap(pos[s[res[i].first]], pos[s[res[i].second]]);
// cout << res[i].first << ' ' << res[i].second << '\n';
// cout << "s: ";
// for (int c : s) cout << c << ' ';
// cout << "\n";
// cout << "p: ";
// for (int c : p) cout << c << ' ';
// cout << "\n";
// cout << "q: ";
// for (int c : q) cout << c << ' ';
// cout << "\n";
// cout << "\n";
}
while (l >= 0 && q[l] == pos[l]) l--;
return (l == -1);
};
for (int len = 1; len <= m; len++) {
if (check(len)) {
for (int i = 0; i < len; i++) {
P[i] = res[i].first;
Q[i] = res[i].second;
}
return len;
}
}
return -1;
}
