#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], idx[N];
for (int i = 0; i < N; i++) ind[i] = i, idx[i] = i, cur[i] = S[i];
set<int> s;
for (int i = 0; i < N; i++)
{
if (ind[i] != p[cur[i]]) s.insert(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]]);
if (s.count(X[i]) && !s.count(Y[i]))
{
s.erase(X[i]), s.insert(Y[i]);
}
else if (!s.count(X[i]) && s.count(Y[i]))
{
s.insert(X[i]), s.erase(Y[i]);
}
int f1 = -1, f2 = -1;
if (!s.empty())
{
f1 = *s.begin();
f2 = idx[p[cur[f1]]];
s.erase(s.begin());
}
if (f1 != -1)
{
swap(cur[f1], cur[f2]);
if (s.count(f2))
{
s.erase(f2), s.insert(f1);
if (ind[f1] == p[cur[f1]]) s.erase(f1);
}
}
}
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], idx[N];
for (int i = 0; i < N; i++) ind[i] = i, idx[i] = i, cur[i] = S[i];
set<int> s;
for (int i = 0; i < N; i++)
{
if (ind[i] != p[cur[i]]) s.insert(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]]);
if (s.count(X[i]) && !s.count(Y[i]))
{
s.erase(X[i]), s.insert(Y[i]);
}
else if (!s.count(X[i]) && s.count(Y[i]))
{
s.insert(X[i]), s.erase(Y[i]);
}
int f1 = -1, f2 = -1;
if (!s.empty())
{
f1 = *s.begin();
f2 = idx[p[cur[f1]]];
s.erase(s.begin());
}
if (f1 != -1)
{
P[i] = f1, Q[i] = f2;
swap(cur[f1], cur[f2]);
if (s.count(f2))
{
s.erase(f2), s.insert(f1);
if (ind[f1] == p[cur[f1]]) s.erase(f1);
}
}
else P[i] = Q[i] = 0;
}
return l;
}
