#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 1e6 + 5;
int p[MXN], ind[MXN], cur[MXN], idx[MXN];
int X[MXN], Y[MXN], S[MXN];
int ok(int mid, int N)
{
vector<int> s;
s.clear();
iota(p, p + 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++) 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]]];
}
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;
}
return ok;
}
int findSwapPairs(int N, int S1[], int M, int x[], int y[], int P[], int Q[])
{
for (int i = 0; i < M; i++) X[i] = x[i], Y[i] = y[i];
for (int i = 0; i < N; i++) S[i] = S1[i];
int l = 0, r = M;
while (l < r)
{
int mid = (l + r) >> 1;
if (ok(mid, N)) r = mid;
else l = mid + 1;
}
vector<int> s;
iota(p, p + 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++) s.push_back(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]]];
}
if (f1 != -1)
{
P[i] = f1, Q[i] = f2;
swap(cur[f1], cur[f2]);
}
else P[i] = Q[i] = 0;
}
return l;
}
