#include "sorting.h"

#include <bits/stdc++.h>

int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    if (0 && std::all_of(X, X + M, [&](int a) { return a == 0; }) && std::all_of(Y, Y + M, [&](int a) { return a == 0; })) {
        std::vector<std::pair<int, int>> ans;

        std::vector<int> used(n);
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                int u = i;
                do {
                    int t = S[u];
                    used[u] = true;
                    if (t != i) {
                        ans.push_back({i, t});
                    }
                    u = t;
                    assert(ans.size() < M);
                } while (u != i);
            }
        }

        for (int i = 0; i < ans.size(); i++) {
            P[i] = ans[i].first;
            Q[i] = ans[i].second;
        }
        return ans.size();
    }

    auto cum = [&](std::vector<std::pair<int, int>> ans) {
        int m = ans.size();
        std::vector<int> p(S, S + n);
        for (int i = 0; i < m; i++) {
            std::swap(p[X[i]], p[Y[i]]);
            std::swap(p[ans[i].first], p[ans[i].second]);
        }
        std::vector<bool> used(n);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                int u = i;
                do {
                    used[u] = true;
                    u = p[u];
                } while (u != i);
                cnt++;
            }
        }
        return cnt;
    };

    static std::mt19937 rnd;

    int m = std::min(M, 4 * n);
    std::vector<std::pair<int, int>> ans(m);
    int sc = cum(ans);
    while (sc < n) {
        int i = rnd() % m;
        std::pair<int, int> pr = {rnd() % n, rnd() % n};
        std::swap(ans[i], pr);
        int sc2 = cum(ans);
        if (sc2 >= sc) {
            if (sc2 > sc) {
                std::cerr << sc2 << "\n";
            }
            sc = sc2;
        } else {
            std::swap(ans[i], pr);
        }
    }

    for (int i = 0; i < ans.size(); i++) {
        P[i] = ans[i].first;
        Q[i] = ans[i].second;
    }
    return ans.size();
}