#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)(v).size()
const int MAXN = 2e5;
int p[MAXN];
bool vis[MAXN];
int findSwapPairs(int n, int P[], int m, int hisX[], int hisY[], int myX[], int myY[]) {
int l = 0, r = m-1; int ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
for (int i=0; i<n; i++) {
p[i] = P[i];
}
for (int i=0; i<=mid; i++) swap(p[hisX[i]], p[hisY[i]]);
for (int i=0; i<n; i++) vis[i] = false;
vector<pair<int, int>> ops;
for (int i=0; i<n; i++) {
int v = i;
while (!vis[v]) {
vis[v] = true;
if (!vis[p[v]]) ops.emplace_back(i, p[v]);
v = p[v];
}
}
if (sz(ops) <= mid+1) {
for (int i=0; i<=mid; i++) {
if (i < sz(ops)) {
myX[i] = ops[i].first; myY[i] = ops[i].second;
} else {
myX[i] = 0; myY[i] = 0;
}
}
r = mid-1;
ans = mid+1;
} else l = mid+1;
}
return ans;
}
