#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)a.size())
typedef vector<int> vint;
#ifndef wambule
#include "sorting.h"
#else
#endif
const int N = 200005, M = 600005;
int n, m, s[N], x[M], y[M], c[N], d[N];
inline void S(int x, int y) {
d[c[x]] = y;
d[c[y]] = x;
swap(c[x], c[y]);
}
void Gc() {
for(int i = 0; i < n; ++i) {
c[i] = s[i];
d[s[i]] = i;
}
}
vector<pair<int, int>> C(int a) {
vector<pair<int, int>> dr(1, {0, 0});
Gc();
for(int i = 0; i < a; ++i) {
S(x[i], y[i]);
}
for(int i = 0; i < n; ++i) {
if(c[i] != i) {
if(sz(dr) == a + 1) {
dr[0].first = 12321;
break;
}
dr.push_back({i, c[i]});
S(i, d[i]);
}
}
while(dr.size() < a + 1) {
dr.push_back({0, 0});
}
return dr;
}
vector<pair<int, int>> D(vector<pair<int, int>> v) {
vector<pair<int, int>> dr;
Gc();
for(int i = 1; i < sz(v); ++i) {
S(x[i - 1], y[i - 1]);
dr.push_back({d[v[i].first], d[v[i].second]});
S(d[v[i].first], d[v[i].second]);
}
return dr;
}
int findSwapPairs(int _n, int _s[], int _m, int _x[], int _y[], int p[], int q[]) {
n = _n; m = _m;
for(int i = 0; i < n; ++i) {
s[i] = _s[i];
}
for(int i = 0; i < m; ++i) {
x[i] = _x[i];
y[i] = _y[i];
}
int l = 0, r = m;
while(l < r) {
int md = (l + r) / 2;
if(C(md)[0].first) {
l = md + 1;
} else {
r = md;
}
}
vector<pair<int, int>> ve = C(l);
vector<pair<int, int>> mo = D(ve);
for(int i = 0; i < sz(mo); ++i) {
p[i] = mo[i].first;
q[i] = mo[i].second;
}
return sz(mo);
}
#ifdef wambule
int nn = 5;
int mm = 5;
int ss[] = {3, 0, 4, 2, 1};
int xx[] = {1, 4, 2, 1, 0};
int yy[] = {1, 0, 3, 4, 4};
int p[M], q[M];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int k = findSwapPairs(nn, ss, mm, xx, yy, p, q);
cout << k << endl;
for(int i = 0; i < k; ++i) {
cout << p[i] << " " << q[i] << endl;
}
return 0;
}
#endif
