#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.
class DisjointSet {
private:
int n, cc;
vector<int> p;
vector<int> sz;
vector<array<int, 3>> history; // (id, p[id], sz[id])
public:
DisjointSet() {}
DisjointSet(int n) : n(n), cc(n) {
p.resize(n);
iota(begin(p), end(p), 0);
sz.assign(n, 1);
history.clear();
}
int Find(int x) {
return p[x] == x ? x : Find(p[x]);
}
int Unite(int x, int y) {
x = Find(x), y = Find(y);
if (x != y) {
cc--;
history.push_back({x, p[x], sz[x]});
history.push_back({y, p[y], sz[y]});
if (sz[x] < sz[y]) {
swap(x, y);
}
sz[x] += sz[y];
p[y] = x;
return 1;
} else {
return 0;
}
}
int CountComponent() {
return cc;
}
int Size() {
return n;
}
void Rollback(int x) {
while (x--) {
cc++;
p[history.back()[0]] = history.back()[1];
sz[history.back()[0]] = history.back()[2];
history.pop_back();
p[history.back()[0]] = history.back()[1];
sz[history.back()[0]] = history.back()[2];
history.pop_back();
}
}
};
const int MAXN = 600005;
DisjointSet D;
vector<array<int, 2>> tree[2 * MAXN];
void AddEdge(int a, int b, int t1, int t2, int n = 1, int l = 0, int r = MAXN - 1) {
if (t2 < l || r < t1 || l > r || t1 > t2) return;
if (t1 <= l && r <= t2) return void(tree[n].push_back({a, b}));
int mid = (l + r) / 2;
int z = n + 2 * (mid - l + 1);
AddEdge(a, b, t1, t2, n + 1, l, mid);
AddEdge(a, b, t1, t2, z, mid + 1, r);
}
void DfsSolve(int &res, int n = 1, int tl = 0, int tr = MAXN - 1) {
int op = 0;
for (auto &e : tree[n]) {
op += D.Unite(e[0], e[1]);
}
if (tl == tr) {
int swaps_needed = D.Size() - D.CountComponent();
if (swaps_needed <= tl + 1) res = min(res, tl + 1);
} else {
int mid = (tl + tr) / 2;
int z = n + 2 * (mid - tl + 1);
DfsSolve(res, n + 1, tl, mid);
DfsSolve(res, z, mid + 1, tr);
}
return D.Rollback(op);
}
int FindOptimalR(int N, vector<int> S, int M, vector<int> X, vector<int> Y) {
vector<int> edge(N); // time
for (int i = 0; i < N; i++) {
edge[i] = 0;
}
for (int i = 0; i < M; i++) {
AddEdge(X[i], S[X[i]], edge[X[i]], i - 1);
AddEdge(Y[i], S[Y[i]], edge[Y[i]], i - 1);
swap(S[X[i]], S[Y[i]]);
edge[X[i]] = edge[Y[i]] = i;
}
for (int i = 0; i < N; i++) {
AddEdge(i, S[i], edge[i], M - 1);
}
D = DisjointSet(N);
int R = M;
DfsSolve(R);
return R;
}
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;
}
