//  ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//  ➡ @roadfromroi ⬅
//  ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#include "sorting.h"
#include "queue"
#define all(x) x.begin(), x.end()
using namespace std;
vector<pair<int, int>> numswp(vector<int> a) {
    priority_queue<int> beba;
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] != i)
            beba.push(i);
    }
    vector<pair<int, int>> swps;
    while (!beba.empty()) {
        int v = beba.top();
        int u = a[v];
        //cout << v << ' ' << u << ' ' << a[v] << ' ' << a[u] << endl;
        if (v != u) {
            swps.push_back({a[v], a[u]});
            swap(a[v], a[u]);
        } else {
            beba.pop();
        }
    }
    if (!is_sorted(all(a))) exit(1);
    return swps;
}
bool lstrg(vector<int> a, int x) {
    priority_queue<int> beba;
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] != i)
            beba.push(i);
    }
    while (!beba.empty()) {
        int v = beba.top();
        int u = a[v];
        //cout << v << ' ' << u << ' ' << a[v] << ' ' << a[u] << endl;
        if (v != u) {
            x--;
            if (x < 0)
                return 0;
            swap(a[v], a[u]);
        } else {
            beba.pop();
        }
    }
    return 1;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    //cout << N << endl;
    vector<int> astrt(N);
    for (int i = 0; i < N; ++i) {
        astrt[i] = S[i];
    }
    int l = -1, r = M;
    while (l + 1 < r) {
        int m = l + r >> 1;
        vector<int> beba = astrt;
        for (int i = 0; i < m; ++i) {
            swap(beba[X[i]], beba[Y[i]]);
        }
        if (lstrg(beba, m))
            r = m;
        else
            l = m;
    }
    int m = r;
    //cout << r << endl;
    vector<int> beba = astrt;
    for (int i = 0; i < m; ++i) {
        swap(beba[X[i]], beba[Y[i]]);
    }
    vector<pair<int, int>> swp = numswp(beba);
    if (swp.size() > r)
        exit(2);
    //cout << r << endl;
    beba = astrt;
    vector<int> ind(N);
    for (int i = 0; i < N; ++i) {
        ind[beba[i]] = i;
    }
    for (int i = 0; i < swp.size(); ++i) {
        swap(ind[beba[X[i]]], ind[beba[Y[i]]]);
        swap(beba[X[i]], beba[Y[i]]);
        P[i] = ind[swp[i].first];
        Q[i] = ind[swp[i].second];
        swap(beba[P[i]], beba[Q[i]]);
        swap(ind[swp[i].first], ind[swp[i].second]);
    }
    for (int i = swp.size(); i < r; ++i) {
        swap(ind[beba[X[i]]], ind[beba[Y[i]]]);
        swap(beba[X[i]], beba[Y[i]]);
        P[i] = 0;
        Q[i] = 0;
    }
    if (!is_sorted(all(beba)))
        exit(1);
    return r;
}
/*
static inline int _readInt() {
    int x;
    cin >> x;
    return x;
}


int main()
{
    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);
    printf("%d\n", ans);
    for (int i = 0; i < ans; ++i)
        printf("%d %d\n", P[i], Q[i]);
    return 0;
}

*/