#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

const int N = 2005;

int n, s[N];
int m, x[N], y[N];
int ansp[N], ansq[N];
int ansr;
int curs[N], s1[N];
bool used[N];

}

int findSwapPairs(int grdn, int grds[], int grdm, int grdx[], int grdy[], int grdp[], int grdq[]) {
	n = grdn;
	for (int i = 0; i < n; ++i) {
		s[i] = grds[i];
	}
	m = grdm;
	for (int i = 0; i < m; ++i) {
		x[i] = grdx[i];
		y[i] = grdy[i];
	}
	for (int i = 0; i < n; ++i) {
		curs[i] = s[i];
	}
	for (int r = 0; r <= m; ++r) {
		vector<vector<int>> kek;
		for (int i = 0; i < n; ++i) {
			used[i] = 0;
		}
		for (int i = 0; i < n; ++i) {
			if (!used[i]) {
				int v = i;
				vector<int> lol;
				while (!used[v]) {
					used[v] = 1;
					lol.push_back(v);
					v = curs[v];
				}
				kek.push_back(lol);
			}
		}
		if (r >= n - (int)kek.size()) {
			ansr = r;
			for (int i = 0; i < n; ++i) {
				s1[i] = curs[i];
			}
			vector<pair<int, int>> swaps;
			for (auto lol : kek) {
				for (int i = 1; i < (int)lol.size(); ++i) {
					swaps.push_back({s1[lol[0]], s1[lol[i]]});
					swap(s1[lol[0]], s1[lol[i]]);
				}
			}
			while ((int)swaps.size() < r) {
				swaps.push_back({0, 0});
			}
			assert((int)swaps.size() == r);
			for (int i = 0; i < n; ++i) {
				s1[i] = curs[i];
			}
			for (int i = r - 1; i >= 0; --i) {
				int x1 = swaps[r - i - 1].first;
				int y1 = swaps[r - i - 1].second;
				int px1 = 0;
				while (s1[px1] != x1) {
					++px1;
				}
				int py1 = 0;
				while (s1[py1] != y1) {
					++py1;
				}
				ansp[i] = px1;
				ansq[i] = py1;
				swap(s1[x[i]], s1[y[i]]);
			}
			break;
		}
		if (r < m) {
			swap(curs[x[r]], curs[y[r]]);
		}
	}
	for (int i = 0; i < ansr; ++i) {
		grdp[i] = ansp[i];
		grdq[i] = ansq[i];
	}
	return ansr;
}