#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
// insertion sort.
vector<int> A(N), at(N);
for (int i = 0; i < N; i++) {
A[i] = S[i];
at[A[i]] = i;
}
for (auto &x : A) cerr << x << " ";
cerr << endl;
int r = 0;
for (int i = N-1; i >= 0; i--) {
if (A[i] == i) continue;
cerr << "ele:" sp A[i] sp "at" sp i << endl;
// perform X[i], Y[i] swap
swap(at[A[X[i]]], at[A[Y[i]]]);
swap(A[X[i]], A[Y[i]]);
cerr << "ermek:" sp A[X[i]] sp "and" sp A[Y[i]] << endl;
// we don't really need to save swaps for st1-3 for now
int at1 = at[i], at2 = i;
int el1 = A[at[i]], el2 = A[i];
P[r] = at1, Q[r] = at2;
r++;
swap(at[el1], at[el2]);
swap(A[at1], A[at2]);
cerr << "aizhan:" sp el1 sp "and" sp el2 << endl;
for (auto &x : A) cerr << x << " ";
cerr << endl;
}
return r;
}
// 3 0 4 2 1
//
