#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int>> vec;
int ind[1<<18], s2[1<<18], seen[1<<18];
int getSwaps(int n, int s[], int m, int x[], int y[]){
vec.clear();
for (int i=0;i<n;i++)
s2[i] = s[i], seen[i] = 0;
for (int i=0;i<m;i++)
swap(s2[x[i]], s2[y[i]]);
for (int i=0;i<n;i++){
if (seen[i])
continue;
while (!seen[i]){
vec.push_back({s2[s2[i]], s2[i]});
seen[i] = 1;
i = s2[i];
}
vec.pop_back();
}
return vec.size();
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]){
int l = -1, r = m;
while (l + 1 < r){
int mid = (l + r) / 2;
if (getSwaps(n, s, mid, x, y) <= mid)
r = mid;
else
l = mid;
}
m = r;
getSwaps(n, s, m, x, y);
for (int i=0;i<n;i++)
ind[s[i]] = i;
reverse(begin(vec), end(vec));
for (int i=0;i<m;i++){
swap(s[x[i]], s[y[i]]);
swap(ind[s[x[i]]], ind[s[y[i]]]);
if (vec.size() > 0){
auto [a, b] = vec.back();
vec.pop_back();
p[i] = ind[a], q[i] = ind[b];
swap(s[p[i]], s[q[i]]);
swap(ind[s[p[i]]], ind[s[q[i]]]);
}
else
p[i] = q[i] = 0;
}
return m;
}
