#include "bits/stdc++.h"
#include "sorting.h"
using namespace std;

mt19937 rnd(228);

int findSwapPairs(int N, int _S[], int M, int X[], int Y[], int P[], int Q[]) {
    vector<int> S(_S, _S + N);

	bool is_sorted = true;
	for (int i = 0; i < N; i++) {
		if (i != P[i]) {
			is_sorted = false;
		}
	}

	if (is_sorted) {
		return 0;
	}

	swap(S[X[0]], S[Y[0]]);

	vector<set<int>> cycles;
	vector<int> num(N, -1);

	for (int i = 0; i < N; i++) {
		if (num[i] != -1) {
			continue;
		}

		cycles.emplace_back();

		int u = i;
		while (num[u] == -1) {
			num[u] = cycles.size() - 1;
			cycles.back().insert(u);
			u = S[u];
		}
	}
	
	for (int i = 1; i < M; i++) {
		if (cycles.size() == N) {
			P[i - 1] = 0;
			Q[i - 1] = 0;
			return i;
		}

		if (cycles.size() == N - 1) {
			for (int j = 0; j < N; j++) {
				if (j != S[j]) {
					P[i - 1] = j;
					Q[i - 1] = S[j];
					break;
				}
			}
			return i;
		}

		int u = X[i];
		int v = Y[i];

		if (num[u] == num[v]) {
			int x = -1;
			for (int y = 0; y < N; y++) {
				if (y != S[y] && S[y] != u && S[y] != v) {
					x = y;
				}
			}

			if (x == -1) {
				P[i - 1] = 0;
				Q[i - 1] = 0;
				P[i] = 0;
				Q[i] = 0;
				
				return i + 1;
			} else {
				P[i - 1] = x;
				Q[i - 1] = S[x];

				cycles.emplace_back();
				cycles.back().insert(S[x]);
				cycles[num[S[x]]].erase(S[x]);
				num[S[x]] = cycles.size() - 1;

				swap(S[P[i - 1]], S[Q[i - 1]]);
			}

			if (u != v) {
				if (rnd() % 2 == 0) {
					swap(u, v);
				}

				swap(S[u], S[v]);
				cycles.emplace_back();
				
				while (num[u] == num[v]) {
					cycles.back().insert(u);
					cycles[num[v]].erase(u);
					num[u] = cycles.size() - 1;
				}
			}
		} else {
			P[i - 1] = X[i];
			Q[i - 1] = Q[i];
		}
	}
	return M;
}