#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 = N + 1;
while (l < r) {
int mid = (l + r) / 2;
vector<int> cur(N);
for (int i = 0; i < N; i++)
cur[i] = S[i];
for (int i = 0; i < mid; i++) {
swap(cur[X[i]], cur[Y[i]]);
}
vector<bool> visited(N);
vector<pair<int, int>> vpii;
for (int i = 0; i < N; i++) {
if (!visited[i]) {
visited[i] = 1;
int tmpi = i;
while (visited[cur[tmpi]] == 0) {
vpii.emplace_back(tmpi, cur[tmpi]);
tmpi = cur[tmpi];
visited[tmpi] = 1;
}
}
}
if (vpii.size() > mid) {
l = mid + 1;
} else {
r = mid;
}
}
vector<int> cur(N);
for (int i = 0; i < N; i++)
cur[i] = S[i];
for (int i = 0; i < l; i++) {
swap(cur[X[i]], cur[Y[i]]);
}
vector<bool> visited(N);
vector<pair<int, int>> vpii;
for (int i = 0; i < N; i++) {
if (!visited[i]) {
visited[i] = 1;
int tmpi = i;
while (visited[cur[tmpi]] == 0) {
vpii.emplace_back(tmpi, cur[tmpi]);
tmpi = cur[tmpi];
visited[tmpi] = 1;
}
}
}
while (vpii.size() < l) {
vpii.push_back({0, 0});
}
for (int i = 0; i < N; i++)
cur[i] = S[i];
vector<int> pos(N);
for (int i = 0; i < N; i++) {
pos[cur[i]] = i;
}
reverse(vpii.begin(), vpii.end());
for (int i = 0; i < l; i++) {
swap(pos[cur[X[i]]], pos[cur[Y[i]]]);
swap(cur[X[i]], cur[Y[i]]);
auto [a, b] = vpii.back();
vpii.pop_back();
P[i] = pos[a], Q[i] = pos[b];
swap(cur[pos[a]], cur[pos[b]]);
swap(pos[a], pos[b]);
}
return l;
}
