#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5;
int n, s[mxN], m, x[mxN], y[mxN], p[mxN], q[mxN], ind[mxN], it;
void set_it(int k) {
while (it < k) {
swap(s[x[it]], s[y[it]]);
it++;
}
while (it > k) {
it--;
swap(s[x[it]], s[y[it]]);
}
}
bool can_do(int k) {
set_it(k);
int cnt = 0;
vector<int> seen(n);
for (int i = 0; i < n; ++i) {
if (!seen[i]) {
seen[i] = 1;
for (int c = s[i]; !seen[c]; c = s[c]) {
seen[c] = 1;
p[cnt] = c;
q[cnt] = s[c];
cnt++;
}
}
}
return cnt <= k;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N, m = M;
copy(S, S+N, s);
copy(X, X+N, x);
copy(Y, Y+N, y);
int lo = 0, hi = N, mid;
while (lo != hi) {
mid = lo+hi >> 1;
if (can_do(mid)) hi = mid;
else lo = mid+1;
}
fill(p,p+n,0);
fill(q,q+n,0);
can_do(lo);
set_it(0);
for (int i = 0; i < n; ++i) ind[s[i]] = i;
for (int i = 0; i < lo; ++i) {
swap(s[x[i]], s[y[i]]);
swap(ind[s[x[i]]], ind[s[y[i]]]);
P[i] = ind[p[i]];
Q[i] = ind[q[i]];
swap(s[P[i]], s[Q[i]]);
swap(ind[s[P[i]]], ind[s[Q[i]]]);
}
return lo;
}
