A permutation p of length n is a sequence of distinct integers p₁, p₂, ..., 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₁, p₂, ..., 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 2k integers x₁, x₂, ..., x_2k — the description of the swap sequence. The printed numbers show that you need to consecutively make swaps (x₁, x₂), (x₃, x₄), ..., (x_2k - 1, x_2k).

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

Note

Sequence x₁, x₂, ..., x_s is lexicographically smaller than sequence y₁, y₂, ..., y_s, if there is such integer r (1 ≤ r ≤ s), that x₁ = y₁, x₂ = y₂, ..., x_r - 1 = y_r - 1 and x_r < y_r.

#	Name	Rating↕	Solved↕
2205E	Simons and Dividing the Rhythm combinatorics data structures dp dsu math string suffix structures strings	2100	1.8k
1780G	Delicious Dessert binary search dsu hashing math number theory string suffix structures	2400	1k
441D	Valera and Swaps constructive algorithms dsu graphs implementation math string suffix structures	2100	1.3k

Problemset