#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifndef WAIMAI
#include "sorting.h"
#endif
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
const int SIZE = 2e5 + 5;
int n;
int a[SIZE], p[SIZE];
bool vs[SIZE];
bool ok(int r, int S[], int X[], int Y[]) {
FOR (i, 0, n - 1) a[i] = S[i], vs[i] = 0;
FOR (i, 0, r - 1) swap(a[X[i]], a[Y[i]]);
int cnt = n;
FOR (i, 0, n - 1) if (!vs[i]) {
cnt--;
for (int cur = i; !vs[cur]; cur = a[cur]) vs[cur] = 1;
}
return cnt <= r;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N;
int l = 0, r = M;
while (l < r) {
int mid = (l + r) / 2;
if (ok(mid, S, X, Y)) r = mid;
else l = mid + 1;
}
FOR (i, 0, n - 1) a[i] = S[i], vs[i] = 0;
FOR (i, 0, r - 1) swap(a[X[i]], a[Y[i]]);
int sz = 0;
FOR (i, 0, n - 1) if (!vs[i]) {
int last = -1, cur = i;
while (!vs[cur]) {
vs[cur] = 1;
if (last != -1) P[sz] = last, Q[sz] = cur, sz++;
last = cur;
cur = a[cur];
}
}
while (sz < r) P[sz] = Q[sz] = 0, sz++;
FOR (i, 0, n - 1) p[S[i]] = i;
FOR (i, 0, r - 1) {
swap(p[S[X[i]]], p[S[Y[i]]]);
swap(S[X[i]], S[Y[i]]);
int a = P[i], b = Q[i];
P[i] = p[a], Q[i] = p[b];
swap(p[S[P[i]]], p[S[Q[i]]]);
swap(S[P[i]], S[Q[i]]);
}
return r;
}
/*
in1
5
4 3 2 1 0
6
0 1
1 2
2 3
3 4
0 1
1 2
out1
3
0 4
1 3
3 4
in2
5
3 0 4 2 1
5
1 1
4 0
2 3
1 4
0 4
out2
3
1 4
4 2
2 2
*/
#ifdef WAIMAI
int main() {
int N, M;
cin >> N;
int *S = (int*)malloc(sizeof(int) * (unsigned int)N);
for (int i = 0; i < N; ++i) cin >> S[i];
cin >> M;
int *X = (int*)malloc(sizeof(int) * (unsigned int)M), *Y = (int*)malloc(sizeof(int) * (unsigned int)M);
for (int i = 0; i < M; ++i) {
cin >> X[i];
cin >> Y[i];
}
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);
cout << ans << '\n';
for (int i = 0; i < ans; ++i) cout << P[i] << ' ' << Q[i] << '\n';
return 0;
}
#endif
