#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
const int MX = 1e5 + 5;
int n, m;
vector<int> s, x, y;
vector<int> a, revA, en, revEn;
bool valid(int t)
{
a = s;
for (int i = 0; i < t; i++)
swap(a[x[i]], a[y[i]]);
for (int i = 0; i < n; i++)
revA[a[i]] = i;
int cnt = 0;
for (int i = 0; i < n; i++)
if (a[i] != i)
{
int j = revA[i];
swap(revA[a[i]], revA[a[j]]);
swap(a[i], a[j]);
cnt++;
}
return cnt <= t;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
n = N, m = M;
s.resize(N), x.resize(N), y.resize(N), a.resize(N), revA.resize(N), en.resize(N), revEn.resize(N);
for (int i = 0; i < N; i++)
{
s.at(i) = S[i];
x.at(i) = X[i];
y.at(i) = Y[i];
}
int R = 0;
int l = 0, r = M;
while (l != r)
{
int mid = (l + r) / 2;
if (!valid(mid))
l = mid + 1;
else
r = mid;
}
R = l;
a = s;
for (int i = 0; i < n; i++)
revA[a[i]] = i;
en = a;
for (int i = 0; i < R; i++)
swap(en[x[i]], en[y[i]]);
for (int i = 0; i < n; i++)
revEn[en[i]] = i;
queue<pair<int, int>> changes;
vector<int> tmp = en;
for (int i = 0; i < n; i++)
if (tmp[i] != i)
{
int j = revEn[i];
swap(revEn[tmp[i]], revEn[tmp[j]]);
swap(tmp[i], tmp[j]);
changes.push({i, j});
}
for (int i = 0; i < R; i++)
{
swap(revA[a[x[i]]], revA[a[y[i]]]);
swap(a[x[i]], a[y[i]]);
if (!changes.empty())
{
auto change = changes.front();
changes.pop();
P[i] = revA[en[change.first]];
Q[i] = revA[en[change.second]];
swap(en[change.first], en[change.second]);
swap(revA[a[P[i]]], revA[a[Q[i]]]);
swap(a[P[i]], a[Q[i]]);
}
else
P[i] = Q[i] = 1;
}
return R;
}
