#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[0], Q[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(p[u], p[v]);
		swap(d[p[u]], d[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(x);
			old_cycle.erase(x);
			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 (cycles.size() == n) {
			return i;
		}

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

		if (X[i] == Y[i]) {
			int u = *not_alone.begin();
			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 (u != p[X[i]] && u != p[Y[i]]) {
					do_swap(u, p[u]);
					break;
				}
			}

			do_swap(X[i], Y[i]);
		} else {
			
		}
	}
	return M;
}