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.

Input

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*$).

Output

In the first line, print integer $*k*$ — the minimum number of swaps.

In the second line, print $2*k*$ integers $*x*_{1}, *x*_{2}, ..., *x*_{2*k*}$ — 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*_{2*k* - 1}, *x*_{2*k*})$.

If there are multiple sequence swaps of the minimum length, print the lexicographically minimum one.

Note

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*} < *y*_{*r*}$.