#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
// build graph and just solve in 3N.
// where does each index go after 3N?
// how do our swaps change the graph
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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;
if (is_sorted(A.begin(), A.end())) return r;
bool ok = false;
while (!ok) {
if (is_sorted(A.begin(), A.end())) return r;
vector<int> o(N);
iota(o.begin(), o.end(), 0);
shuffle(o.begin(), o.end(), rng);
for (int j = N-1; j >= 0; j--) {
int i = o[j];
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;
if (is_sorted(A.begin(), A.end())) return r;
// for (auto &x : A) cerr << x << " ";
// cerr << endl;
}
}
return r;
}
// 3 0 4 2 1
//
