#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);
	vector<int> D(N);

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

	if (is_sorted) {
		return 0;
	}

	auto do_swap = [&](int u, int v) {
		swap(S[u], S[v]);
		swap(D[S[u]], D[S[v]]);
	};


	do_swap(X[0], 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;

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

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

				do_swap(u, v);
				cycles.emplace_back();
				
				while (num[u] == num[v]) {
					cycles.back().insert(u);
					cycles[num[v]].erase(u);
					num[u] = cycles.size() - 1;
				}
			}
		} else {
			if (u != D[u]) {
				P[i - 1] = u;
				Q[i - 1] = D[u];

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

				do_swap(P[i - 1], Q[i - 1]);
			} else if (v != D[v]) {
				P[i - 1] = v;
				Q[i - 1] = D[v];

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

				do_swap(P[i - 1], Q[i - 1]);
			} else {
				P[i - 1] = X[i];
				Q[i - 1] = Y[i];
			}
		}
	}
	return M;
}