#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "sorting.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int L = 0, R = M;
auto check = [&](int mid) {
vector <int> p(N);
for (int i = 0; i < N; ++i) p[i] = S[i];
for (int i = 0; i < mid; ++i) swap(p[X[i]], p[Y[i]]);
int comp = 0;
vector <int> vis(N, 0);
for (int u = 0; u < N; ++u) {
if (vis[u]) continue;
++comp;
int v = u;
do {
vis[v] = 1;
v = p[v];
} while (u != v);
}
return (N - comp <= mid);
};
while (L < R) {
int mid = L + R >> 1;
if (check(mid)) R = mid;
else L = mid + 1;
}
vector <int> pos(N);
for (int i = 0; i < L; ++i) swap(S[X[i]], S[Y[i]]);
vector <int> vis(N, 0);
vector <pair <int, int>> need;
for (int u = 0; u < N; ++u) {
if (vis[u]) continue;
int v = u;
do {
if (S[v] != u) need.push_back({v, S[v]});
vis[v] = 1;
v = S[v];
} while (u != v);
}
for (int i = L - 1; i >= 0; --i) swap(S[X[i]], S[Y[i]]);
while (need.size() < L) need.push_back({0, 0});
for (int i = 0; i < N; ++i) pos[S[i]] = i;
for (int i = 0; i < L; ++i) {
swap(pos[S[X[i]]], pos[S[Y[i]]]);
swap(S[X[i]], S[Y[i]]);
auto &[u, v] = need[i];
u = pos[u], v = pos[v];
P[i] = u, Q[i] = v;
swap(pos[S[u]], pos[S[v]]);
swap(S[u], S[v]);
}
return L;
}
//static char _buffer[1024];
//static int _currentChar = 0;
//static int _charsNumber = 0;
//static FILE *_inputFile, *_outputFile;
//
//static inline int _read() {
// if (_charsNumber < 0) {
// exit(1);
// }
// if (!_charsNumber || _currentChar == _charsNumber) {
// _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
// _currentChar = 0;
// }
// if (_charsNumber <= 0) {
// return -1;
// }
// return _buffer[_currentChar++];
//}
//
//static inline int _readInt() {
// int c, x, s;
// c = _read();
// while (c <= 32) c = _read();
// x = 0;
// s = 1;
// if (c == '-') {
// s = -1;
// c = _read();
// }
// while (c > 32) {
// x *= 10;
// x += c - '0';
// c = _read();
// }
// if (s < 0) x = -x;
// return x;
//}
//
//
//int main()
//{
// _inputFile = fopen("sorting.in", "rb");
// _outputFile = fopen("sorting.out", "w");
// int N, M;
// N = _readInt();
// int *S = (int*)malloc(sizeof(int) * (unsigned int)N);
// for (int i = 0; i < N; ++i)
// S[i] = _readInt();
// M = _readInt();
// int *X = (int*)malloc(sizeof(int) * (unsigned int)M), *Y = (int*)malloc(sizeof(int) * (unsigned int)M);
// for (int i = 0; i < M; ++i) {
// X[i] = _readInt();
// Y[i] = _readInt();
// }
// int *P = (int*)malloc(sizeof(int) * (unsigned int)M), *Q = (int*)malloc(sizeof(int) * (unsigned int)M);
// int ans = findSwapPairs(N, S, M, X, Y, P, Q);
// fprintf(_outputFile, "%d\n", ans);
// for (int i = 0; i < ans; ++i)
// fprintf(_outputFile, "%d %d\n", P[i], Q[i]);
// return 0;
//}
//
