#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n;
int S[N], X[N * 3], Y[N * 3];
int A[N], B[N], C[N], D[N];
vector< pair<int, int> > vec;
bool check(int len) {
vec.clear();
for (int i = 0; i < n; ++i) A[i] = S[i];
for (int i = 0; i < n; ++i) B[i] = i;
for (int i = 0; i < n; ++i) C[B[i]] = i;
for (int i = 0; i < len; ++i) {
int x = C[X[i]], y = C[Y[i]];
swap(C[X[i]], C[Y[i]]);
swap(B[x], B[y]);
}
for (int i = 0; i < n; ++i) D[A[i]] = i;
for (int i = 0; i < n; ++i) {
if (D[i] == C[i]) continue;
int x = D[i], y = C[i];
vec.push_back({x, y});
swap(D[i], D[A[y]]);
swap(A[x], A[y]);
}
while (vec.size() < len) vec.push_back({0, 0});
return vec.size() == len;
}
int findSwapPairs(int _n, int _S[], int m, int _X[], int _Y[], int P[], int Q[]) {
n = _n;
for (int i = 0; i < n; ++i) {
S[i] = _S[i];
}
for (int i = 0; i < m; ++i) {
X[i] = _X[i];
Y[i] = _Y[i];
}
int l = 0, r = m - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid; else l = mid + 1;
}
int len = l;
check(len);
for (int i = 0; i < n; ++i) B[i] = i;
for (int i = 0; i < n; ++i) C[B[i]] = i;
for (int i = 0; i < len; ++i) {
int x = C[X[i]], y = C[Y[i]];
swap(C[Y[i]], C[X[i]]);
swap(B[x], B[y]);
x = vec[i].first, y = vec[i].second;
P[i] = B[x], Q[i] = B[y];
}
return len;
}
