A9516 | Valera and Swaps

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<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.