E. Сортировка циклами
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив из $$$n$$$ целых положительных чисел $$$a_1, a_2, \dots, a_n$$$. К массиву можно применять следующие операции: выбрать несколько различных индексов этого массива $$$i_1, i_2, \dots, i_k$$$ ($$$1 \le i_j \le n$$$) и переместить число, стоящее на позиции $$$i_1$$$ на позицию $$$i_2$$$, число стоящее на позиции $$$i_2$$$ на позицию $$$i_3$$$, ..., число на позиции $$$i_k$$$ на позицию $$$i_1$$$. То есть сдвинуть элементы по циклу $$$i_1 \to i_2 \to \ldots i_k \to i_1$$$.

К примеру, если у вас есть $$$n=4$$$, массив $$$a_1=10, a_2=20, a_3=30, a_4=40$$$, и вы выбрали три индекса $$$i_1=2$$$, $$$i_2=1$$$, $$$i_3=4$$$, то получившийся массив будет $$$a_1=20, a_2=40, a_3=30, a_4=10$$$.

Вам дано целое неотрицательное число $$$s$$$. Отсортируйте массив с помощью минимально возможного количества таких операций, при условии, что сумма размеров циклов для всех операций не превосходит $$$s$$$, или скажите, что это невозможно.

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

Первая строка ввода содержит числа $$$n$$$ и $$$s$$$ ($$$1 \leq n \leq 200\,000$$$, $$$0 \leq s \leq 200\,000$$$) — число элементов массива и верхнюю границу на сумму длин циклов. Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ — элементы массива ($$$1 \leq a_i \leq 10^9$$$).

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

Если невозможно упорядочить массив, используя циклы с суммарной длиной меньше либо равной $$$s$$$, выведите единственное число «-1».

В противном случае, в первой строке выведите единственное число $$$q$$$ — минимальное количество операций, требующееся для того, чтобы упорядочить массив.

На следующих $$$2 \cdot q$$$ строках выведите описания операций в том порядке, в каком их нужно применять к массиву. Описание $$$i$$$-й операции начинается со строки с единственным числом $$$k$$$ ($$$1 \le k \le n$$$) — длины цикла (т.е. количества выбранных индексов). Следующая строка должна содержать $$$k$$$ различных целых чисел $$$i_1, i_2, \dots, i_k$$$ ($$$1 \le i_j \le n$$$) — сами индексы.

Суммарная длина циклов должна быть меньше или равна $$$s$$$, и массив должен быть упорядочен после применениях всех $$$q$$$ операций. Если есть несколько возможных ответов с оптимальным $$$q$$$, выведите любой из них.

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

В первом примере также возможно упорядочить массив двумя операциями суммарной длины 5: сначала применить цикл $$$1 \to 4 \to 1$$$ (длины 2), потом применить цикл $$$2 \to 3 \to 5 \to 2$$$ (длины 3). Однако, это неверный ответ, поскольку в задаче требуется минимизировать количество операций, а минимальное число операций для этого теста равно единице.

Во втором примере, можно упорядочить массив двумя циклами общей длины 4 $$$1 \to 2 \to 1$$$ и $$$3 \to 4 \to 3$$$. Но невозможно циклами длиной не больше 3.

В третьем примере, массив уже упорядочен, поэтому операции не нужны. Общая длина пустого множества циклов принимается равной нулю.