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

mt19937 rnd(228);

bool is_sorted(const vector<int> &s) {
	int n = (int)s.size();
	for (int i = 0; i + 1 < n; i++) {
		if (s[i + 1] < s[i]) {
			return false;
		}
	}
	return true;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	int n = N;

	vector<int> p(S, S + N);
	vector<int> d(S, S + N);

	if (is_sorted(p)) {
		return 0;
	}

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

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

	for (int u = 0; u < n; u++) {
		d[p[u]] = u;

		if (num[u] != -1) {
			continue;
		}

		cycles.emplace_back();
		int x = (int)cycles.size() - 1;
		auto &cycle = cycles.back();

		int v = u;
		while (num[v] == -1) {
			num[v] = x;
			cycle.insert(v);
			v = p[v];
		}
	}

	set<int> not_alone;

	for (int u = 0; u < n; u++) {
		if (p[u] != u) {
			not_alone.insert(u);
		}
	}

	auto do_swap = [&](int u, int v) -> void {
		assert(num[u] == num[v]);
		
		not_alone.erase(u);
		not_alone.erase(v);

		if (p[u] == v || rnd() % 2) {
			swap(u, v);
		}

		swap(d[p[u]], d[p[v]]);
		swap(p[u], p[v]);

		cycles.emplace_back();
		int x = (int)cycles.size() - 1;
		auto &old_cycle = cycles[num[u]];
		auto &new_cycle = cycles.back();

		while (num[u] != x) {
			new_cycle.insert(u);
			old_cycle.erase(u);
			num[u] = x;
			u = p[u];
		}

		if (p[u] != u) {
			not_alone.insert(u);
		}

		if (p[v] != v) {
			not_alone.insert(v);
		}
	};

	for (int i = 0; i < M; i++) {
		P[i] = Q[i] = 0;
	}

	for (int i = 1; i < M; i++) {
		if (not_alone.empty()) {
			return i;
		}

		if (not_alone.size() == 2) {
			int u = *not_alone.begin();
			P[i - 1] = u;
			Q[i - 1] = p[u];
			return i;
		}

		if (X[i] == Y[i]) {
			int u = *not_alone.begin();
			P[i - 1] = u;
			Q[i - 1] = p[u];
			do_swap(u, p[u]);
		} else if (num[X[i]] == num[Y[i]]) {
			if (not_alone.size() == 2) {
				return i + 1;
			}

			for (int u : not_alone) {
				if (p[u] != X[i] && p[u] != Y[i]) {
					P[i - 1] = u;
					Q[i - 1] = p[u]; 
					do_swap(u, p[u]);
					break;
				}
			}

			do_swap(X[i], Y[i]);
		} else {
			int x = X[i];
			int y = Y[i];

			if (p[x] == x && p[y] == y) {
				int u = *not_alone.begin();
				P[i - 1] = u;
				Q[i - 1] = p[u];
				do_swap(u, p[u]);
				
				cycles[num[x]].insert(y);
				cycles[num[y]].erase(y);

				num[y] = num[x];

				swap(d[p[x]], d[p[y]]);
				swap(p[x], p[y]);

				not_alone.insert(x);
				not_alone.insert(y);
			} else {
				if (d[y] != y) {
					swap(x, y);
				}
				
				P[i - 1] = x;
				Q[i - 1] = d[x];

				do_swap(x, d[x]);

				cycles[num[x]].erase(x);
				cycles[num[y]].insert(x);

				num[x] = num[y];

				swap(d[p[x]], d[p[y]]);
				swap(p[x], p[y]);

				not_alone.insert(x);
				not_alone.insert(y);
			}
		}
	}
	return M;
}