Valera and Swaps

题意翻译

时间限制 $1s$ | 空间限制 $256M$ #### 题目描述 给出长度为$n$的排列$p$，定义长度为$n$的*本体排列* 为满足$p_i=i$（$1\le i\le n$）的排列。互换操作是指对于$(i,j)$（$1\le i,j\le n$）互换$p_i,p_j$在排列中的位置。设$f(p)$为将排列$p$通过互换操作转变为本体排列的最小操作数。请求出如何花费最小的步数将排列$p$转变为排列$q$使得$f(q)=m$。 #### 输入格式 第一行一个正整数$n$ （$1\le n\le 3000$），表示排列$p$的长度。 第二行$n$个正整数$p_i$ （$1\le p_i\le n$），意义见题目描述。 第三行一个整数$m$ （$0\le m<n$），意义见题目描述。 #### 输出格式 第一行一个正整数$k$，表示最小操作数。 第二行$2k$个正整数$x_i$，描述操作方案，表示进行了$(x_1,x_2),(x_3,x_4),...,(x_{2k-1},x_{2k})$的互换操作。 如果有多种方案，输出$x$数组字典序最小的一种。 #### 样例输入输出： | 样例1输入 | 样例1输出 | 样例2输入 | 样例2输出 | | --------------------- | ------------- | --------------------- | --------- | | 5<br/>1 2 3 4 5<br/>2 | 2<br/>1 2 1 3 | 5<br/>2 1 4 5 3<br/>2 | 1<br/>1 2 |

题目描述

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 $ p_{1},p_{2},...,p_{n} $ ( $ 1<=p_{i}<=n $ ) — Valera's initial permutation. The last line contains integer $ m $ ( $ 0<=m&lt;n $ ).

输出格式

In the first line, print integer $ k $ — the minimum number of swaps. In the second line, print $ 2k $ integers $ x_{1},x_{2},...,x_{2k} $ — 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_{2k-1},x_{2k}) $ . If there are multiple sequence swaps of the minimum length, print the lexicographically minimum one.

输入输出样例

输入样例 #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 

说明

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}&lt;y_{r} $ .