Codeforces Round 252 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

dsu

graphs

implementation

math

string suffix structures

*2100

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Valera and Swaps

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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*_{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.

Examples

Input

5

1 2 3 4 5

2

Output

2

1 2 1 3

Input

5

2 1 4 5 3

2

Output

1

1 2

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/01/2024 11:50:24 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|