D. Валера и обмены
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановкой p длины n называется последовательность различных целых чисел p1, p2, ..., pn (1 ≤ pi ≤ n). Перестановка называется тождественной, если для всех i выполняется равенство pi = i.

Обмен (i, j) — это операция, в результате которой элементы pi и pj меняются местами в перестановке. Пусть f(p) — это минимальное число обменов, которое нужно совершить, чтобы перестановка p стала тождественной.

Валера очень хочет узнать, как за минимальное число обменов из перестановки p получить перестановку q, такую, что f(q) = m. Помогите ему в этом.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 3000) — длина перестановки p. Во второй строке записано n различных целых чисел p1, p2, ..., pn (1 ≤ pi ≤ n) — изначальная перестановка Валеры. В последней строке записано целое число m (0 ≤ m < n).

Выходные данные

В первой строке выведите целое число k — минимальное число обменов.

Во второй строке выведите 2k целых чисел x1, x2, ..., x2k — описание последовательности обменов. Выведенные числа обозначают, что необходимо последовательно произвести обмены (x1, x2), (x3, x4), ..., (x2k - 1, x2k).

Если существует несколько последовательностей обменов минимальной длины, выведите лексикографически минимальную.

Примеры
Входные данные
5
1 2 3 4 5
2
Выходные данные
2
1 2 1 3
Входные данные
5
2 1 4 5 3
2
Выходные данные
1
1 2
Примечание

Последовательность x1, x2, ..., xs лексикографически меньше последовательности y1, y2, ..., ys, если существует такое целое число r (1 ≤ r ≤ s), что x1 = y1, x2 = y2, ..., xr - 1 = yr - 1 и xr < yr.