#include "sorting.h"
#include <bits/stdc++.h>
#define outvec(v) cout << #v << " = "; for (int x: v) { cout << x << " "; } cout << endl
using namespace std;
typedef pair<int, int> pii;
vector<pii> qr;
vector<int> Sr, perm, inv, Xr, Yr, tmp, inv_tmp;
void qry_raw(int p, int q, bool ok){
swap(inv[perm[p]], inv[perm[q]]);
swap(perm[p], perm[q]);
if (ok) qr.push_back({p, q});
// for (int i=0;i<(int)perm.size();i++) assert(inv[perm[i]]==i);
}
void swap_indices_vec(vector<int> &vec, vector<int> &inv_vec, int p, int q){
swap(inv_vec[vec[p]], inv_vec[vec[q]]);
swap(vec[p], vec[q]);
}
int sim_cur = 0, cur = 0, Mr;
void sim_vec(vector<int> &vec, vector<int> &inv_vec, int rep){
while(rep--){
assert(sim_cur<Mr);
swap_indices_vec(vec, inv_vec, Xr[sim_cur], Yr[sim_cur]);
sim_cur++;
}
}
void swap_elements(int p, int q){
assert(cur<Mr);
qry_raw(Xr[cur], Yr[cur], false);
qry_raw(inv[p], inv[q], true);
cur++;
}
bool maybe(int t){
int N = (int)perm.size();
for (int i=0;i<N;i++) perm[i] = Sr[i], inv[perm[i]] = i;
qr.clear(); cur = 0, sim_cur = 0;
int cn = t;
tmp = perm, inv_tmp = inv; sim_vec(tmp, inv_tmp, cn);
for (int i=0;i<N;i++){
if (tmp[i] != i){
if (cn == 0) break;
cn--;
swap_elements(tmp[i], i);
swap_indices_vec(tmp, inv_tmp, i, inv_tmp[i]);
}
}
while(cn--) swap_elements(0, 0);
bool ok = true;
for (int i=0;i<N;i++) ok &= tmp[i] == i;
return ok;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
Sr.resize(N), perm.resize(N), inv.resize(N), Xr.resize(M), Yr.resize(M); Mr=M;
for (int i=0;i<N;i++) perm[i] = Sr[i] = S[i];
for (int i=0;i<M;i++) Xr[i] = X[i], Yr[i] = Y[i];
for (int i=0;i<N;i++) inv[perm[i]] = i;
// ----------------------------
int lo = 0, hi = M; hi++;
while(lo < hi){
int mid = lo + (hi - lo)/2;
if (maybe(mid)) hi = mid;
else lo = mid+1;
}
int best = lo; maybe(best); vector<pii> bestqr = qr;
// ----------------------------
for (int i=0;i<best;i++){
P[i] = bestqr[i].first;
Q[i] = bestqr[i].second;
}
return best;
}
