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

pair<int, int> any(int N, vector<int> S, int a, int b) {
	vector<int> pos(N);

	for (int i = 0; i < N; i++) {
		pos[S[i]] = i;
	}

	for (int i = 0; i < N; i++) {
		if (pos[i] != i) {
			if (i != a && pos[i] != b && i != b && pos[i] != a) {
				return {i, pos[i]};
			}
		}
	}
	
	return {0, 0};
}

int cost(int N, vector<int> s) {
	vector<int> pos(N);
	
	for (int i = 0; i < N; i++) {
		pos[s[i]] = i;
	}

	int cnt = 0;

	for (int i = 0; i < N; i++) {
		if (pos[i] != i) {
			cnt += 1;

			int x = s[i];
			int y = pos[i];

			pos[x] = y;
			pos[i] = i;

			swap(s[i], s[y]);
		}
	}

	return cnt;
}

int findSwapPairs(int N, int _S[], int M, int X[], int Y[], int P[], int Q[]) {
    vector<int> S(_S, _S + N);
	
	if (cost(N, S) == 0) {
		return 0;
	}

	for (int i = 0; i < M; i++) {
		swap(S[X[i]], S[Y[i]]);

		int cur = cost(N, S);

		if (cur == 0) {
			P[i] = Q[i] = 0;
			return i + 1;
		}

		if (cur == 1) {
			vector<int> a;
			for (int i = 0; i < N; i++) {
				if (S[i] != i) {
					a.push_back(i);
				}
			}
			P[i] = a.front();
			Q[i] = a.back();
			return i + 1;
		}

		pair<int, int> best = {0, 0};
		int val_bast = N;

		for (int x = 0; x < N; x++) {
			for (int y = x; y < N; y++) {
				swap(S[x], S[y]);
				swap(S[X[i + 1]], S[Y[i + 1]]);

				if (cost(N, S) < val_bast) {
					val_bast = cost(N, S);
					best = {x, y};
				}

				swap(S[X[i + 1]], S[Y[i + 1]]);
				swap(S[x], S[y]);
			}
		}

		P[i] = best.first;
		Q[i] = best.second;

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