#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define nl '\n'
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
vector<int> comp(n);
for(int i = 0; i < n; i++) comp[i] = s[i];
sort(all(comp));
comp.erase(unique(all(comp)), comp.end());
for(int i = 0; i < n; i++) s[i] = lower_bound(all(comp), s[i]) - comp.begin();
vector<int> pos(n), ele(n), a(n);
vector<pair<int, int>> a1(n);
for(int i = 0; i < n; i++) {
a[i] = s[i];
a1[i] = {s[i], i};
}
auto b = a;
sort(all(b));
auto b1 = a1;
sort(all(b1));
auto check = [&](int R) {
for(int i = 0; i < n; i++) a[i] = s[i];
for(int i = 0; i < R; i++) swap(a[x[i]], a[y[i]]);
vector<vector<int>> A(n), B(n);
for(int i = 0; i < n; i++) {
if(a[i] == b[i]) pos[i] = i;
else A[a[i]].pb(i), B[b[i]].pb(i);
}
for(int i = 0; i < n; i++) {
auto &val = A[i];
auto &val2 = B[i];
assert(val.size() == val2.size());
for(int j = 0; j < (int)val.size(); j++) {
pos[val[j]] = val2[j];
}
}
int cnt = 0;
for(int i = 0; i < n; i++) {
int j = i;
while(j != pos[j]) {
int k = pos[j];
swap(a[j], a[k]);
swap(pos[j], pos[k]);
cnt++;
}
}
return cnt <= R;
};
int l = 0, r = m;
while(l < r) {
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
auto construct = [&](int R) {
for(int i = 0; i < n; i++) a1[i] = {s[i], i};
for(int i = 0; i < R; i++) swap(a1[x[i]], a1[y[i]]);
vector<vector<int>> A(n), B(n);
for(int i = 0; i < n; i++) {
int key1 = a1[i].first;
int key2 = b1[i].first;
if(key1 == key2) pos[i] = i;
else A[key1].pb(i), B[key2].pb(i);
}
for(int i = 0; i < n; i++) {
auto &val = A[i];
auto &val2 = B[i];
assert(val.size() == val2.size());
for(int j = 0; j < (int)val.size(); j++) {
pos[val[j]] = val2[j];
}
}
vector<pair<int, int>> idx;
for(int i = 0; i < n; i++) {
int j = i;
while(j != pos[j]) {
int k = pos[j];
idx.pb({ a1[j].second, a1[k].second });
// idx.pb({ j, k });
swap(a1[j], a1[k]);
swap(pos[j], pos[k]);
}
}
assert( (int)idx.size() <= R );
while( (int)idx.size() < R ) idx.pb({0, 0});
// for(auto [i, j] : idx) {
// cout << i << ' ' << j << nl;
// }
// cout << nl;
// cout << "INIT: " << nl;
// for(int j = 0; j < n; j++) cout << j << ' ';
// cout << nl;
// for(int j = 0; j < n; j++) cout << s[j] << ' ';
// cout << nl;
iota(all(ele), 0);
iota(all(pos), 0);
for(int i = 0; i < R; i++) {
// cout << nl;
// for(auto j : pos) cout << j << ' ';
// cout << nl;
// swap( s[x[i]], s[y[i]] );
int ok1 = ele[x[i]], ok2 = ele[y[i]];
swap(ele[x[i]], ele[y[i]]);
swap( pos[ok1], pos[ok2] );
// for(auto j : pos) cout << j << ' ';
// cout << nl;
// cout << nl;
// for(int j = 0; j < n; j++) cout << s[j] << ' ';
// cout << nl;
auto [i1, i2] = idx[i];
ok1 = pos[i1], ok2 = pos[i2];
p[i] = ok1, q[i] = ok2;
// swap( s[ok1], s[ok2] );
swap( ele[ok1], ele[ok2] );
swap( pos[i1], pos[i2] );
// for(int j = 0; j < n; j++) cout << s[j] << ' ';
// cout << nl;
}
};
// cout << nl;
construct(l);
return l;
}
