长度为 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。