#include "sorting.h"
#include "bits/stdc++.h"
using namespace std;
const int MXN = 200005;
int n, m;
int seq[MXN];
pair<int, int> plan[MXN];
vector<pair<int, int> > ans;
bool works(int sw) {
// cout << "try: " << sw << ' ';
ans.clear();
int nsw[n];
for (int i=0; i<n; i++) nsw[i] = seq[i];
int where[n];
for (int i=0; i<sw; i++) {
int a = plan[i].first, b = plan[i].second;
swap(nsw[a], nsw[b]);
}
for (int i=0; i<n; i++) {
where[nsw[i]] = i;
}
int need = 0;
for (int i=0; i<n; i++) {
if (nsw[i] == i) continue;
need++;
int ati = nsw[i];
int whei = where[i];
where[ati] = whei;
where[i] = i;
nsw[i] = i;
nsw[ati] = whei;
ans.push_back(make_pair(i, whei));
}
// cout << (need <= sw) << endl;
// if (sw == 3) return true;
return need <= sw;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N;
m = M;
for (int i=0; i<n; i++) seq[i] = S[i];
for (int i=0; i<m; i++) {
plan[i].first = X[i];
plan[i].second = Y[i];
}
int low = 0;
int high = M + 1;
while (low + 1 < high) {
int mid = (low + high) / 2;
if (works(mid)) {
high = mid;
}
else {
low = mid;
}
}
if (works(low)) {
works(low);
for (int i=0; i<low; i++) {
P[i] = ans[i].first;
Q[i] = ans[i].second;
}
return low;
}
else {
works(high);
for (int i=0; i<high; i++) {
P[i] = ans[i].first;
Q[i] = ans[i].second;
}
return high;
}
}
