#ifndef LOCAL
#include "sorting.h"
#endif
#include <vector>
#include <iostream>
#include <numeric>
#include <algorithm>
#include <queue>
template <class T>
using Vec = std::vector<T>;
struct DSU {
Vec<int> par;
DSU(const int n): par(n, -1) { }
int find(const int u) {
return par[u] < 0 ? u : par[u] = find(par[u]);
}
bool unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
if (par[x] > par[y]) {
std::swap(x, y);
}
par[x] += par[y];
par[y] = x;
return true;
}
};
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int ok = M, ng = -1;
while (ok - ng > 1) {
int md = (ok + ng) / 2;
Vec<int> perm(N);
Vec<int> inv(N);
std::iota(perm.begin(), perm.end(), 0);
std::iota(inv.begin(), inv.end(), 0);
const auto swap = [&](const int i, const int j) {
std::swap(perm[i], perm[j]);
inv[perm[i]] = i;
inv[perm[j]] = j;
};
for (int i = 0; i < md; ++i) {
swap(X[i], Y[i]);
}
std::queue<std::pair<int, int>> que;
{
Vec<int> to(N);
for (int i = 0; i < N; ++i) {
to[S[i]] = inv[i];
}
Vec<char> used(N);
for (int i = 0; i < N; ++i) {
if (!used[i]) {
Vec<int> path;
{
int u = i;
while (!used[u]) {
path.push_back(u);
used[u] = true;
u = to[u];
}
}
for (int j = 0; j + 1 < (int) path.size(); ++j) {
que.emplace(path[0], path[j + 1]);
}
}
}
}
if ((int) que.size() > md) {
ng = md;
continue;
}
ok = md;
for (int i = 0; i < N; ++i) {
perm[i] = S[i];
inv[S[i]] = i;
}
for (int i = 0; i < md; ++i) {
swap(X[i], Y[i]);
if (que.empty()) {
P[i] = Q[i] = 0;
}
else {
const auto [x, y] = que.front();
que.pop();
const auto s = inv[x];
const auto t = inv[y];
P[i] = s;
Q[i] = t;
swap(s, t);
}
}
}
return ok;
}
#ifdef LOCAL
int main() {
int N;
std::cin >> N;
int S[100] = {};
for (int i = 0; i < N; ++i) {
std::cin >> S[i];
}
int M;
std::cin >> M;
int X[100] = {};
int Y[100] = {};
for (int i = 0; i < M; ++i) {
std::cin >> X[i] >> Y[i];
}
int P[100] = {};
int Q[100] = {};
int R = findSwapPairs(N, S, M, X, Y, P, Q);
for (int i = 0; i < R; ++i) {
std::swap(S[X[i]], S[Y[i]]);
std::swap(S[P[i]], S[Q[i]]);
}
std::cout << R << '\n';
for (int i = 0; i < N; ++i) {
std::cout << S[i] << " \n"[i + 1 == N];
}
return 0;
}
#endif
