#include "sorting.h"
#include "bits/stdc++.h"
using namespace std;
int f(int r, int n, int S[], int X[], int Y[], int p[], int q[]){
int P[n], pos[n];
for (int i = 0; i < n; i++)
P[i] = S[i];
//Ermek's first R swap operations
for (int i = 0; i < r; i++)
swap(P[X[i]], P[Y[i]]);
for (int i = 0; i < n; i++)
pos[P[i]] = i;
int r_prime = 0;
for (int i = 0; i < n; i++){
if (pos[i] == i)
continue;
int j = pos[i];
p[r_prime] = P[i];
q[r_prime] = P[j];
r_prime += 1;
swap(pos[P[i]], pos[P[j]]);
swap(P[i], P[j]);
}
return r_prime;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
bool ok = true;
for (int i = 0; i < N; i++)
ok &= (S[i] == i);
if (ok)
return 0;
int r = 1;
while (r <= M){
if (f(r, N, S, X, Y, P, Q) <= r)
break;
r += 1;
}
assert(r <= M);
int r_prime = f(r, N, S, X, Y, P, Q);
int pos[N];
for (int i = 0; i < N; i++)
pos[S[i]] = i;
for (int i = 0; i < r_prime; i++){
swap(pos[S[X[i]]], pos[S[Y[i]]]);
swap(S[X[i]], S[Y[i]]);
int p = pos[P[i]], q = pos[Q[i]];
swap(pos[S[p]], pos[S[q]]);
swap(S[p], S[q]);
P[i] = p;
Q[i] = q;
}
for (int i = r_prime; i < r; i++)
P[i] = Q[i] = 0;
return r;
}
