#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> 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++;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
perm.resize(N), inv.resize(N), Xr.resize(M), Yr.resize(M); Mr=M;
for (int i=0;i<N;i++) perm[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;
// ----------------------------
tmp = perm, inv_tmp = inv; sim_vec(tmp, inv_tmp, M);
int cn = M;
while(cn--){
bool done = false;
for (int i=0;i<N;i++){
if (tmp[i] != i){
swap_elements(tmp[i], i);
swap_indices_vec(tmp, inv_tmp, i, inv_tmp[i]);
done = true;
break;
}
}
if (!done) swap_elements(0, 0);
}
reverse(qr.begin(), qr.end());
// ----------------------------
for (int i=0;i<(int)qr.size();i++){
P[i] = qr[i].first;
Q[i] = qr[i].second;
}
return (int)qr.size();
}
