#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
int p[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];
for (int i=0; i<mid; i++) swap(p[hisX[i]], p[hisY[i]]);
vector<pair<int, int>> ops(mid, make_pair(0, 0));
for (int op=0; op<mid; op++) {
for (int i=0; i<n; i++) {
if (p[i] != i) {
int pos = 0;
for (int j=i+1; j<n; j++) {
if (p[j] == i) {
pos = j;
break;
}
}
ops[op] = {i, pos};
swap(p[i], p[pos]);
break;
}
}
}
bool check = true;
for (int i=0; i<n and check; i++) {
if (p[i] != i) check = false;
}
if (check) {
r = mid-1;
for (int op=0; op<mid; op++) {
myX[op] = ops[op].first;
myY[op] = ops[op].second;
}
ans = mid;
} else l = mid+1;
}
return ans;
}
