#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;
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);
}
int sim_cur = 0, cur = 0, Mr;
void sim_vec(vector<int> &vec, int rep){
while(rep--){
assert(sim_cur<Mr);
swap(vec[Xr[sim_cur]], vec[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 unreal = true;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
assert(unreal);unreal=false;
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;
// ----------------------------
sim_cur=0;
cur=0;
tmp = perm; sim_vec(tmp, M);
int cn = M;
while(cn--){
bool done = false;
for (int i=0;i<N;i++){
if (tmp[i] != i){
int j=0;
while(j<N && tmp[j] != i) j++;
swap_elements(tmp[i], tmp[j]);
swap(tmp[i], tmp[j]);
done = true;
break;
}
}
if (!done) swap_elements(0, 0);
}
// ----------------------------
for (int i=0;i<(int)qr.size();i++){
P[i] = qr[i].first;
Q[i] = qr[i].second;
}
return (int)qr.size();
}
