P6305 [eJOI 2018] Cycle Sort

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`.

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

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.

[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$. | Subtask ID | Score | Constraints | | :-----------: | :-----------: | :-----------: | | $1$ | $0$ | Samples | | $2$ | $5$ | $n, s \leq 2$ and $1 \leq a_i \leq 2$ | | $3$ | $5$ | $n \leq 5$ | | $4$ | $5$ | $1 \leq a_i \leq 2$ | | $5$ | $10$ | $a$ is a permutation, $s = 2 \times n$ | | $6$ | $10$ | $a$ is a permutation, $n \leq 10^3$ | | $7$ | $15$ | $a$ is a permutation | | $8$ | $15$ | $s = 2 \times n$ | | $9$ | $15$ | $n \leq 10^3$ | | $10$ | $20$ | No special constraints | --- Source: [eJOI2018](http://ejoi2018.org/) Problem F "Cycle Sort". Note: The translation comes from [LOJ](https://loj.ac/problem/2818). Translated by ChatGPT 5