#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 p[N], ind[N], cur[N], idx[N], u[N];
vector<int> s;
int l = 0, r = M;
while (l < r)
{
int mid = (l + r) >> 1;
s.clear();
iota(p, p + N, 0);
iota(u, u + N, 0);
for (int i = 0; i < mid; i++) swap(p[X[i]], p[Y[i]]);
for (int i = 0; i < N; i++) ind[i] = i, idx[i] = i, cur[i] = S[i];
for (int i = 0; i < N; i++)
{
if (ind[i] != p[cur[i]]) s.push_back(ind[i]);
}
for (int i = 0; i < mid; i++)
{
swap(idx[ind[X[i]]], idx[ind[Y[i]]]);
swap(ind[X[i]], ind[Y[i]]);
swap(cur[X[i]], cur[Y[i]]);
while (!s.empty() && s.back() == p[cur[idx[s.back()]]])
{
s.pop_back();
}
int f1 = -1, f2 = -1;
if (!s.empty())
{
f1 = idx[s.back()];
f2 = idx[p[cur[f1]]];
s.pop_back();
}
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;
}
s.clear();
iota(p, p + N, 0);
iota(u, u + N, 0);
for (int i = 0; i < l; i++) swap(p[X[i]], p[Y[i]]);
for (int i = 0; i < N; i++) ind[i] = i, idx[i] = i, cur[i] = S[i];
for (int i = 0; i < N; i++)
{
if (ind[i] != p[cur[i]]) s.push_back(ind[i]);
}
for (int i = 0; i < l; i++)
{
swap(idx[ind[X[i]]], idx[ind[Y[i]]]);
swap(ind[X[i]], ind[Y[i]]);
swap(cur[X[i]], cur[Y[i]]);
while (!s.empty() && s.back() == p[cur[idx[s.back()]]])
{
s.pop_back();
}
int f1 = -1, f2 = -1;
if (!s.empty())
{
f1 = idx[s.back()];
f2 = idx[p[cur[f1]]];
s.pop_back();
}
if (f1 != -1)
{
P[i] = f1, Q[i] = f2;
swap(cur[f1], cur[f2]);
}
else P[i] = Q[i] = 0;
}
return l;
}
