Description

Given a sequence $\{a_i\}$ of length $n$, you may perform the following operation multiple times:

Choose $k$ distinct indices $i_1, i_2 \cdots, i_k$ (where $1 \leq i_j \leq n$), then move $a_{i_1}$ to index $i_2$, move $a_{i_2}$ to index $i_3$, $\ldots$, move $a_{i_{k-1}}$ to index $i_k$, and move $a_{i_k}$ to index $i_1$.

In other words, you may rotate the elements in the following order: $i_1 \rightarrow i_2 \rightarrow \cdots \rightarrow i_k \rightarrow i_1$.

For example: $n = 4$, $\{a_i\} = \{10, 20, 30, 40\}$, $i_1 = 2$, $i_2 = 3$, $i_3 = 4$. After the operation, the sequence $a$ becomes $\{10, 40, 20, 30\}$.

Your task is to sort the entire sequence into non-decreasing order using the minimum number of operations. Note that, over all operations, the total number of chosen indices must not exceed $s$. If there is no such method (no solution), output -1.

Input Format

The first line contains two integers, $n$ and $s$.

The second line contains $n$ integers $a_{1\cdots n}$, representing the sequence $\{a_i\}$.

Output Format

If there is no solution, output only -1.

Otherwise, output an integer $q$ on the first line (it may be $0$, see Sample 3), representing the minimum number of operations needed.

Then output $2 \times q$ lines describing each operation.

For each operation, first output an integer $k$, the number of indices chosen in this operation, then output $k$ integers $i_{1\cdots k}$ on the next line.

When the number of operations $q$ is minimized, you may output any feasible solution.

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

6 9
6 5 4 3 2 1

2
6
1 6 2 5 3 4
3
3 2 1

6 8
6 5 4 3 2 1

3
2
3 4
4
1 6 2 5
2
2 1

Hint

[Explanation for Sample 1]

You can sort the array using two operations $1 \rightarrow 4 \rightarrow 1$ and $2 \rightarrow 3 \rightarrow 5 \rightarrow 2$, but this will get WA, because your task is to minimize $q$, and the optimal answer has $q = 1$.

One feasible method is $1 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 5 \rightarrow 1$, which is exactly the sample output.

[Explanation for Sample 2]

The minimum possible total number of chosen indices over all operations is $4$ (one feasible method is $1 \rightarrow 2 \rightarrow 1$ and $3 \rightarrow 4 \rightarrow 3$), so there is no solution.

[Explanation for Sample 3]

The array is already sorted, so no operation is needed.

Additional note: Samples 4 and 5 satisfy the constraints of Subtasks 6 and 7.

[Constraints]

For $100\%$ of the testdata: $1 \leq n \leq 2 \times 10^5$, $0 \leq s \leq 2 \times 10^5$, $1 \leq a_i \leq 10^9$.

Source: eJOI2018 Problem F "Cycle Sort".

Note: The translation comes from LOJ.

Translated by ChatGPT 5