CF441D.Valera and Swaps

A permutation p of length n is a sequence of distinct integers _p_1, _p_2, ..., p__n (1 ≤ p__i ≤ n). A permutation is an identity permutation, if for any i the following equation holds p__i = i.

A swap (i, j) is the operation that swaps elements p__i and p__j 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.

长度为 $n$ 的一个排列 $p$ 是由互不相同的整数 $p_1,\,p_2,\,\dots,\,p_n$（其中 $1\le p_i\le n$）构成的序列。若对任意 $i$ 均有 $p_i = i$，则称该排列为恒等排列。

交换操作 $(i,\,j)$ 表示将排列中位置 $i$ 和 $j$ 上的元素 $p_i$ 与 $p_j$ 互换。记 $f(p)$ 为将排列 $p$ 变为恒等排列所需的最少交换次数。

瓦列拉想知道：如何通过最少次数的交换操作，将排列 $p$ 变为某个排列 $q$，使得 $f(q) = m$？请你帮助他实现这一目标。

The first line contains integer n (1 ≤ n ≤ 3000) — the length of permutation p. The second line contains n distinct integers _p_1, _p_2, ..., p__n (1 ≤ p__i ≤ n) — Valera's initial permutation. The last line contains integer m (0 ≤ m < n).

第一行包含一个整数 $n$（$1 \leq n \leq 3000$）—— 排列 $p$ 的长度。
第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \dots, p_n$（$1 \leq p_i \leq n$）—— Valera 的初始排列。
最后一行包含一个整数 $m$（$0 \leq m < n$）。

In the first line, print integer k — the minimum number of swaps.

In the second line, print 2_k_ integers _x_1, _x_2, ..., x_2_k — the description of the swap sequence. The printed numbers show that you need to consecutively make swaps (_x_1, _x_2), (_x_3, _x_4), ..., (x_2_k - 1, x_2_k).

If there are multiple sequence swaps of the minimum length, print the lexicographically minimum one.

第一行输出整数 $k$ —— 最少交换次数。

第二行输出 $2k$ 个整数 $x_1,\,x_2,\,\dots,\,x_{2k}$ —— 交换序列的描述。所输出的数字表示需依次执行交换 $(x_1,\,x_2),\,(x_3,\,x_4),\,\dots,\,(x_{2k-1},\,x_{2k})$。

若存在多个长度最小的交换序列，请输出字典序最小的一个。

Sequence _x_1, _x_2, ..., x__s is lexicographically smaller than sequence _y_1, _y_2, ..., y__s, if there is such integer r (1 ≤ r ≤ s), that _x_1 = _y_1, _x_2 = _y_2, ..., x__r - 1 = y__r - 1 and x__r < y__r.

序列 $x_1, x_2, \dots, x_s$ 在字典序上小于序列 $y_1, y_2, \dots, y_s$，当且仅当存在某个整数 $r$（$1 \le r \le s$），使得 $x_1 = y_1,\, x_2 = y_2,\, \dots,\, x_{r-1} = y_{r-1}$，且 $x_r < y_r$。