#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
int p[MAXN], pVal[MAXN];
int findSwapPairs(int n, int P[], int m, int hisX[], int hisY[], int myX[], int myY[]) {
int l = 0, r = m; int ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
for (int i=0; i<n; i++) {
p[i] = P[i];
pVal[P[i]] = i;
}
for (int i=0; i<mid; i++) swap(p[hisX[i]], p[hisY[i]]);
vector<bool> mark(n, false);
vector<pair<int, int>> ops;
for (int i=0; i<n; i++) {
vector<int> cycle;
int j = i;
// cerr << "cycle:";
while (!mark[j]) {
mark[j] = true;
cycle.push_back(p[j]);
// cerr << j << ' ';
j = p[j];
}
for (int k=1; k<(int)cycle.size(); k++)
ops.emplace_back(cycle[0], cycle[k]);
}
bool check = (int)ops.size() <= mid;
for (int i=0; i<n and check; i++) p[i] = P[i];
for (int i=0; i<mid and check; i++) {
// executa i dele
int val1 = p[hisX[i]], val2 = p[hisY[i]];
swap(p[hisX[i]], p[hisY[i]]);
swap(pVal[val1], pVal[val2]);
// faz sua i
myX[i] = pVal[ops[i].first];
myY[i] = pVal[ops[i].second];
}
// cerr << mid << ':' << check << endl;
if (check) {
r = mid-1;
ans = mid;
} else l = mid+1;
}
return ans;
}
