A permutation *p* of length *n* is a sequence of distinct integers *p*<sub class="lower-index">1</sub>, *p*<sub class="lower-index">2</sub>, ..., *p*<sub class="lower-index">*n*</sub> (1 ≤ *p*<sub class="lower-index">*i*</sub> ≤ *n*). A permutation is an identity permutation, if for any *i* the following equation holds *p*<sub class="lower-index">*i*</sub> = *i*. 

A swap (*i*, *j*) is the operation that swaps elements *p*<sub class="lower-index">*i*</sub> and *p*<sub class="lower-index">*j*</sub> in the permutation. Let's assume that *f*(*p*) is the minimum number of swaps that you need to make the permutation *p* an identity permutation. 

Valera wonders, how he can transform permutation *p* into any permutation *q*, such that *f*(*q*) = *m*, using the minimum number of swaps. Help him do that.
The first line contains integer *n* (1 ≤ *n* ≤ 3000) — the length of permutation *p*. The second line contains *n* distinct integers *p*<sub class="lower-index">1</sub>, *p*<sub class="lower-index">2</sub>, ..., *p*<sub class="lower-index">*n*</sub> (1 ≤ *p*<sub class="lower-index">*i*</sub> ≤ *n*) — Valera's initial permutation. The last line contains integer *m* (0 ≤ *m* &lt; *n*).
#include <bits/stdc++.h>
using namespace std;

const int maxn = 6000 + 10;
int p[maxn], cid[maxn], prv[maxn], sz[maxn], pa[maxn];
bool v[maxn];
deque<int> cycle;

int find(int now) { return now == pa[now] ? now : pa[now] = find(pa[now]); }
void merge(int a, int b) { a = find(a); b = find(b); pa[a] = b; }

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) pa[i] = i;
    for (int i = 1; i <= n; ++i) cin >> p[i], prv[p[i]] = i;
    int m; cin >> m;
    int c = n - m, cnow = 0;
    for (int i = 1; i <= n; ++i) if (!v[i]) {
        int now = i; ++cnow;
        while (!v[now]) {
            // cycle[cnow].push_back(now);
            ++sz[cnow];
            cid[now] = cnow;
            v[now] = true;
            merge(now, p[now]);
            now = p[now];
        }
    }
    // cout << "ok" << endl;
    int ptr = 1, nid = cnow + 1;
    int tmp = cnow;
    vector<pair<int, int>> ans;
    // cout << "cnow = " << cnow << endl;
    while (cnow < c) {
        while (sz[cid[ptr]] == 1) ++ptr;
        int kmin = n + 1, cur = p[ptr];
        while (cur != ptr) {
            kmin = min(kmin, cur);
            cur = p[cur];
        }
        if (kmin == n + 1) {
            ++ptr;
            continue;
        }
        ans.emplace_back(ptr, kmin);
        swap(p[ptr], p[kmin]);
        
        // cout << "ptr = " << ptr << endl;
        // if (p[ptr] < prv[ptr]) {
            // ans.emplace_back(ptr, p[ptr]);
            // cid[p[ptr]] = nid++;
            // sz[cid[p[ptr]]] = 1;
            // --sz[cid[ptr]];
            // prv[p[p[ptr]]] = ptr;
            // p[ptr] = p[p[ptr]];
        // } else {
            // ans.emplace_back(ptr, prv[ptr]);
            // cid[ptr] = nid++;
            // --sz[cid[prv[ptr]]];
            // sz[cid[ptr]] = 1;
            // p[prv[ptr]] = p[ptr];
            // prv[p[ptr]] = prv[ptr];
        // }
        ++cnow;
    }
    ptr = 2;
    while (cnow > c) {
        while (find(ptr) == find(1)) ++ptr;
        ans.emplace_back(1, ptr); 
        merge(ptr, 1);
        --cnow;
    }
    for (auto& i : ans) {
        int a = min(i.first, i.second), b = max(i.first, i.second);
        i = make_pair(a, b);
    }
    sort(ans.begin(), ans.end());
    // vector<int> csize;
    // for (int i = 1; i <= cnow; ++i) csize.push_back(i);
    // sort(csize.begin(), csize.end(), [&](const int& a, const int& b) { return cycle[a].size() > cycle[b].size(); });
    // size_t ptr = 0;
    // while (cnow < c) {
        // while (ptr < csize.size() && cycle[csize[ptr]].size() < 2) ++ptr;
        // ans.emplace_back(cycle[csize[ptr]][0], cycle[csize[ptr]][1]);
        // cycle[csize[ptr]].pop_front();
        // ++cnow;
    // }
    // while (cnow > c) {
        // while (ptr) 
    // }
    assert((int)ans.size() == abs(tmp - c));
    cout << ans.size() << endl;
    for (auto i : ans) cout << i.first << ' ' << i.second << ' ';
    return 0;
;}
