#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
vector<pii> qr;
vector<int> perm, inv, Xr, Yr;
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});
// cout << "check id: "; for (int x: perm) cout << inv[x] << " "; cout << endl;
}
int cur = 0, Mr;
void qry(int p, int q){
assert(cur<Mr);
qry_raw(Xr[cur], Yr[cur], false);
qry_raw(p, 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;
if (perm[0] != 0 && perm[1] != 0){
int p0 = inv[0];
if (perm[0] == 1) qry(p0, 0); // because they swap first
else qry(p0, 1);
}
if (perm[0] != 1 && perm[1] != 1){
int p1 = inv[1];
if (perm[0] == 0) qry(p1, 0); // because they swap first
else qry(p1, 1);
}
while(1){
bool done = false;
for (int i=2;i<N;i++){
if (perm[i] != i){
int pi = inv[i]; // N-ish R
qry(i, pi);
done = true;
break;
}
}
if (!done) break;
}
if (!is_sorted(perm.begin(), perm.end())) qry(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();
}
