Перестановкой p длины n называется последовательность различных целых чисел p1, p2, ..., pn (1 ≤ pi ≤ n). Перестановка называется тождественной, если для всех i выполняется равенство pi = i.
Обмен (i, j) — это операция, в результате которой элементы pi и pj меняются местами в перестановке. Пусть f(p) — это минимальное число обменов, которое нужно совершить, чтобы перестановка p стала тождественной.
Валера очень хочет узнать, как за минимальное число обменов из перестановки p получить перестановку q, такую, что f(q) = m. Помогите ему в этом.
Выходные данные
В первой строке выведите целое число k — минимальное число обменов.
Во второй строке выведите 2k целых чисел x1, x2, ..., x2k — описание последовательности обменов. Выведенные числа обозначают, что необходимо последовательно произвести обмены (x1, x2), (x3, x4), ..., (x2k - 1, x2k).
Если существует несколько последовательностей обменов минимальной длины, выведите лексикографически минимальную.
Примечание
Последовательность x1, x2, ..., xs лексикографически меньше последовательности y1, y2, ..., ys, если существует такое целое число r (1 ≤ r ≤ s), что x1 = y1, x2 = y2, ..., xr - 1 = yr - 1 и xr < yr.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 3 4 5
2
|
2
1 2 1 3
|
|
2
|
5
2 1 4 5 3
2
|
1
1 2
|