Вам дан массив из \(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\), или скажите, что это невозможно.
Выходные данные
Если невозможно упорядочить массив, используя циклы с суммарной длиной меньше либо равной \(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: сначала применить цикл \(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.
В третьем примере, массив уже упорядочен, поэтому операции не нужны. Общая длина пустого множества циклов принимается равной нулю.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5
3 2 3 1 1
|
1
5
1 4 2 3 5
|
|
2
|
4 3
2 1 4 3
|
-1
|
|
3
|
2 0
2 2
|
0
|