// In the name of Allah
#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, q;
const int maxn = 2e5 + 7;
int A1[maxn], A2[maxn];
int ind[maxn], indx[maxn];
int mark[maxn]; vector<pii> ls;
void dfs(int v) {
mark[v] = 1; int u = A1[v];
if (!mark[u]) dfs(u);
}
bool ok(int n, int S[], int q, int X[], int Y[]) {
for (int i = 0; i < n; i++) A1[i] = S[i];
for (int i = 0; i < q; i++) {
int i1 = X[i], i2 = Y[i];
swap(A1[i1], A1[i2]);
}
fill(mark, mark + n, 0); int c = 0;
for (int i = 0; i < n; i++) {
if (!mark[i]) {
dfs(i); c++;
}
}
return (n - c <= q);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int l = -1, r = M;
while (r - l > 1) {
int mid = (l + r) / 2;
if (ok(N, S, mid, X, Y)) r = mid;
else l = mid;
}
n = N; q = r;
for (int i = 0; i < n; i++) {
A1[i] = S[i]; A2[i] = S[i];
ind[S[i]] = i; indx[S[i]] = i;
}
for (int i = 0; i < q; i++) {
int i1 = X[i], i2 = Y[i];
P[i] = 0; Q[i] = 0;
swap(A2[i1], A2[i2]);
swap(indx[A2[i1]], indx[A2[i2]]);
}
ls.clear();
for (int i = 0; i < n; i++) {
if (A2[i] == i) continue;
int i1 = i, i2 = indx[i];
ls.pb(Mp(A2[i1], A2[i2]));
swap(A2[i1], A2[i2]);
swap(indx[A2[i1]], indx[A2[i2]]);
}
for (int i = 0; i < q; i++) {
int i1 = X[i], i2 = Y[i];
swap(A1[i1], A1[i2]);
swap(ind[A1[i1]], ind[A1[i2]]);
if (i < len(ls)) {
int x1 = ls[i].F, x2 = ls[i].S;
P[i] = ind[x1]; Q[i] = ind[x2];
}
i1 = P[i], i2 = Q[i];
swap(A1[i1], A1[i2]);
swap(ind[A1[i1]], ind[A1[i2]]);
}
return q;
}
