#include "sorting.h"
#ifdef DEBUG
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define cmin(a, b) a=min(a, b)
#define cmax(a, b) a=max(a, b)
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
int n, m;
vector<int> a, pos;
void make_swap(int x, int y) {
if (x==y) return;
swap(a[x], a[y]);
pos[a[x]]=x, pos[a[y]]=y;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n=N; for (int i=0; i<n; i++) a.pb(S[i]);
pos.resize(n);
int l=0, r=n, ans=n;
while (l<=r) {
int mid=(l+r)/2, t=mid;
auto base=a;
for (int i=0; i<t; i++) swap(a[X[i]], a[Y[i]]);
vector<pair<int, int>> changes; set<int> wrong;
for (int i=0; i<n; i++) if (a[i]!=i) wrong.insert(i);
for (int i=0; i<n; i++) pos[a[i]]=i;
while (!wrong.empty()) {
int i=*wrong.begin(); wrong.erase(wrong.begin());
int j=pos[i];
make_swap(i, j);
if (a[j]==j && a[i]==i) wrong.erase(j);
changes.pb({a[i], a[j]});
}
a=base;
if (sz(changes)<=t) {
for (int i=0; i<n; i++) pos[a[i]]=i;
for (int i=0; i<t; i++) {
make_swap(X[i], Y[i]);
if (i<sz(changes)) make_swap(pos[changes[i].fi], pos[changes[i].second]), P[i]=pos[changes[i].fi], Q[i]=pos[changes[i].se];
else P[i]=0, Q[i]=0;
}
a=base;
ans=t;
r=mid-1;
} else l=mid+1;
}
return ans;
}
