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.
输入描述:
The first line contains integer n (1 ≤ n ≤ 3000) — the length of permutation p. The second line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n) — Valera's initial permutation. The last line contains integer m (0 ≤ m n).
输出描述:
In the first line, print integer k — the minimum number of swaps.In the second line, print 2k integers x1, x2, ..., x2k — the description of the swap sequence. The printed numbers show that you need to consecutively make swaps (x1, x2), (x3, x4), ..., (x2k - 1, x2k). If there are multiple sequence swaps of the minimum length, print the lexicographically minimum one.
示例1
输入
5<br />1 2 3 4 5<br />2<br />5<br />2 1 4 5 3<br />2<br />
输出
2<br />1 2 1 3 1<br />1 2
备注:
Sequence x1, x2, ..., xs is lexicographically smaller than sequence y1, y2, ..., ys, if there is such integer r(1 ≤ r ≤ s), that x1 = y1, x2 = y2, ..., xr - 1 = yr - 1 and xr yr.
加载中...