#include <bits/stdc++.h>
int findSwapPairs(int n, int s[], int m, int u[], int v[], int uu[], int vv[]) {
std::vector <int> a(s, s + n);
std::vector <int> o(s, s + n);
int l = 0, r = m;
std::vector <std::pair <int, int>> last;
while (l < r) {
int mid = (l + r) >> 1;
a = o;
std::vector <bool> vis(n, false);
std::vector <std::pair <int, int>> now;
for (int i = 0; i < mid; i++) {
std::swap(a[u[i]], a[v[i]]);
}
auto f = [&] (auto&& self, int ind, int root) -> void {
vis[ind] = true;
now.emplace_back(ind, a[ind]);
if (a[ind] != root) {
self(self, a[ind], root);
}
};
for (int i = 0; i < n; i++) {
if (!vis[i] && a[i] != i) {
f(f, a[i], i);
}
}
if ((int) now.size() > mid) {
l = mid + 1;
} else {
r = mid;
}
}
a = o;
std::vector <bool> vis(n, false);
auto f = [&] (auto&& self, int ind, int root) -> void {
vis[ind] = true;
last.emplace_back(ind, a[ind]);
if (a[ind] != root) {
self(self, a[ind], root);
}
};
for (int i = 0; i < l; i++) {
std::swap(a[u[i]], a[v[i]]);
}
for (int i = 0; i < n; i++) {
if (!vis[i] && a[i] != i) {
f(f, a[i], i);
}
}
a = o;
std::vector <int> inv(n);
for (int i = 0; i < n; i++) {
inv[a[i]] = i;
}
for (int i = 0; i < l; i++) {
std::swap(a[u[i]], a[v[i]]);
std::swap(inv[a[u[i]]], inv[a[v[i]]]);
if (i < (int) last.size()) {
uu[i] = inv[last[i].first];
vv[i] = inv[last[i].second];
std::swap(a[uu[i]], a[vv[i]]);
std::swap(inv[a[uu[i]]], inv[a[vv[i]]]);
} else {
uu[i] = vv[i] = 0;
}
}
return l;
}
