← 返回题目列表

Codeforces · 441/D

D. 瓦莱拉和掉期

中文机器翻译题面 查看原题

长度为 n 的排列 p 是不同整数 p1, p2, ..., pn (1 ≤ pi ≤ n) 的序列。如果对于任何 i,以下等式成立 pi = i,则排列是恒等排列。

swap (i, j) 是交换排列中的元素 pi 和 pj 的操作。假设 f(p) 是使排列 p 成为恒等排列所需的最小交换次数。

Valera 想知道他如何使用最少的交换次数将排列 p 转换为任意排列 q,使得 f(q) = m。帮助他做到这一点。

输入

第一行包含整数 n (1 ≤ n ≤ 3000) — 排列 p 的长度。第二行包含 n 个不同的整数 p1, p2, ..., pn (1 ≤ pi ≤ n) — Valera 的初始排列。最后一行包含整数 m (0 ≤ m < n)。

输出

在第一行中,打印整数 k — 最小交换次数。

在第二行中,打印 2k 个整数 x1, x2, ..., x2k — 交换序列的描述。打印的数字表明您需要连续进行交换 (x1, x2), (x3, x4), ..., (x2k - 1, x2k)。

如果存在多个最小长度的序列交换,则打印字典顺序最小的一个。

示例

输入 #1

5
1 2 3 4 5
2

输出 #1

2
1 2 1 3

输入 #2

5
2 1 4 5 3
2

输出 #2

1
1 2

注意

序列 x1, x2, ..., xs 按字典顺序小于序列 y1, y2, ..., ys,如果存在这样的整数 r (1 ≤ r ≤ s),即 x1 = y1, x2 = y2, ..., xr - 1 = yr - 1 且 xr < yr。