#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
int l = 0, r = M;
while (l < r)
{
int mid = (l + r) >> 1;
int p[N];
iota(p, p + N, 0);
for (int i = 0; i < mid; i++) swap(p[X[i]], p[Y[i]]);
int ind[N], cur[N];
for (int i = 0; i < N; i++) ind[i] = i, cur[i] = S[i];
for (int i = 0; i < mid; i++)
{
swap(ind[X[i]], ind[Y[i]]);
swap(cur[X[i]], cur[Y[i]]);
int f1 = -1, f2 = -1;
for (int j = 0; j < N; j++)
{
if (ind[j] != p[cur[j]])
{
f1 = j;
for (int k = 0; k < N; k++)
{
if (ind[k] == p[cur[j]])
{
f2 = k;
break;
}
}
break;
}
}
if (f1 != -1) swap(cur[f1], cur[f2]);
}
int ok = 1;
for (int i = 0; i < N; i++)
{
if (ind[i] != p[cur[i]]) ok = 0;
}
if (ok) r = mid;
else l = mid + 1;
}
int p[N];
iota(p, p + N, 0);
for (int i = 0; i < l; i++) swap(p[X[i]], p[Y[i]]);
int ind[N], cur[N];
for (int i = 0; i < N; i++) ind[i] = i, cur[i] = S[i];
for (int i = 0; i < l; i++)
{
swap(ind[X[i]], ind[Y[i]]);
swap(cur[X[i]], cur[Y[i]]);
int f1 = -1, f2 = -1;
for (int j = 0; j < N; j++)
{
if (ind[j] != p[cur[j]])
{
f1 = j;
for (int k = 0; k < N; k++)
{
if (ind[k] == p[cur[j]])
{
f2 = k;
break;
}
}
break;
}
}
if (f1 != -1)
{
P[i] = f1, Q[i] = f2;
swap(cur[f1], cur[f2]);
}
else P[i] = Q[i] = 0;
}
return l;
}
