#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
// Solution:
// Add edge i -> S[i]. Minimum number of swaps needed is N - count_cycles(S)
// Cycles always form, we can simply maintain number of connected components with
// dynamic connectivity. We can recover answer easily. However this is not fast
// enough to fit in the time limit, as this approach is O(M log M log N).
//
// To optimize, observe that number of cycles after each swap only change by 1.
// For -1 swap pairs, we can use our turn to swap the same pair. Thus we can
// binary search the answer. This yields O(N log M).
class DisjointSet {
private:
int n, cc;
vector<int> p;
vector<int> sz;
public:
DisjointSet() {}
DisjointSet(int n) : n(n), cc(n) {
p.resize(n);
iota(begin(p), end(p), 0);
sz.assign(n, 1);
}
int Find(int x) {
return p[x] == x ? x : p[x] = Find(p[x]);
}
int Unite(int x, int y) {
x = Find(x), y = Find(y);
if (x == y) return 0;
cc--;
if (sz[x] < sz[y]) {
swap(x, y);
}
sz[x] += sz[y];
p[y] = x;
return 1;
}
int CountComponent() {
return cc;
}
};
int FindOptimalR(int N, vector<int> S, int M, vector<int> X, vector<int> Y) {
auto Check = [&](int R) {
DisjointSet D(N);
for (int i = 0; i < R; i++) {
swap(S[X[i]], S[Y[i]]);
}
for (int i = 0; i < N; i++) {
D.Unite(i, S[i]);
}
int swaps_needed = N - D.CountComponent();
for (int i = R - 1; i >= 0; i--) {
swap(S[X[i]], S[Y[i]]);
}
return swaps_needed <= R;
};
int lo = 1, hi = M;
while (lo < hi) {
int md = (lo + hi) / 2;
if (Check(md)) {
hi = md;
} else {
lo = md + 1;
}
}
return lo;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
if (is_sorted(S, S + N)) return 0;
int R = FindOptimalR(N, vector<int>(S, S + N), M, vector<int>(X, X + M), vector<int>(Y, Y + M));
vector<int> pos(N), seq(N);
for (int i = 0; i < N; i++) {
pos[S[i]] = i;
seq[i] = S[i];
}
vector<array<int, 2>> operations;
for (int i = 0; i < R; i++) {
swap(S[X[i]], S[Y[i]]);
}
for (int i = 0; i < N; i++) {
while (i != S[i]) {
operations.push_back({S[i], S[S[i]]});
swap(S[i], S[S[i]]);
}
}
while (operations.size() < R) {
operations.push_back({0, 0});
}
for (int i = 0; i < R; i++) {
swap(seq[X[i]], seq[Y[i]]);
pos[seq[X[i]]] = X[i];
pos[seq[Y[i]]] = Y[i];
P[i] = pos[operations[i][0]];
Q[i] = pos[operations[i][1]];
swap(seq[P[i]], seq[Q[i]]);
pos[seq[P[i]]] = P[i];
pos[seq[Q[i]]] = Q[i];
}
return R;
}
