512002 - 互换

【题目描述】互换(swap)

给定一个由数字1~n组成的序列,输出字典序最小且次数最少的两两交换方式,使得交换后的序列可以通过最少m次交换得到 [1,2,...,n]的序列。

输入

第一行为一个整数n(1≤n≤3000),表示序列的长度。 第二行为排列的数p1, p2,...,pn(1≤pi≤n)。 第三行为一个整数m (0≤m<n)。

输出

第一行输出一个整数K,表示最少交换操作数。 第二行输出2K个数,用于描述交换过程。如果有多个最小长度的序列交换,则打印按字典顺序排列的最小长度。

样例

输入

5
1 2 3 4 5
2

输出

2
1 2 1 3

输入

5
2 1 4 5 3
2

输出

1
1 2
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题