Cycle sort
Contest: Codeforces Round 500 (Div. 1) [based on EJOI]
Difficulty rating: 3100
Tags: dsu, math

You are given an array of $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$. You can perform the following operation any number of times: select several distinct indices $$$i_1, i_2, \dots, i_k$$$ ($$$1 \le i_j \le n$$$) and move the number standing at the position $$$i_1$$$ to the position $$$i_2$$$, the number at the position $$$i_2$$$ to the position $$$i_3$$$, ..., the number at the position $$$i_k$$$ to the position $$$i_1$$$. In other words, the operation cyclically shifts elements: $$$i_1 \to i_2 \to \ldots i_k \to i_1$$$.

For example, if you have $$$n=4$$$, an array $$$a_1=10, a_2=20, a_3=30, a_4=40$$$, and you choose three indices $$$i_1=2$$$, $$$i_2=1$$$, $$$i_3=4$$$, then the resulting array would become $$$a_1=20, a_2=40, a_3=30, a_4=10$$$.

Your goal is to make the array sorted in non-decreasing order with the minimum number of operations. The additional constraint is that the sum of cycle lengths over all operations should be less than or equal to a number $$$s$$$. If it's impossible to sort the array while satisfying that constraint, your solution should report that as well.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$s$$$ ($$$1 \leq n \leq 200\,000$$$, $$$0 \leq s \leq 200\,000$$$)—the number of elements in the array and the upper bound on the sum of cycle lengths.

The next line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$—elements of the array ($$$1 \leq a_i \leq 10^9$$$).

Output format:
If it's impossible to sort the array using cycles of total length not exceeding $$$s$$$, print a single number "-1" (quotes for clarity).

Otherwise, print a single number $$$q$$$— the minimum number of operations required to sort the array.

On the next $$$2 \cdot q$$$ lines print descriptions of operations in the order they are applied to the array. The description of $$$i$$$-th operation begins with a single line containing one integer $$$k$$$ ($$$1 \le k \le n$$$)—the length of the cycle (that is, the number of selected indices). The next line should contain $$$k$$$ distinct integers $$$i_1, i_2, \dots, i_k$$$ ($$$1 \le i_j \le n$$$)—the indices of the cycle.

The sum of lengths of these cycles should be less than or equal to $$$s$$$, and the array should be sorted after applying these $$$q$$$ operations.

If there are several possible answers with the optimal $$$q$$$, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, it's also possible to sort the array with two operations of total length 5: first apply the cycle $$$1 \to 4 \to 1$$$ (of length 2), then apply the cycle $$$2 \to 3 \to 5 \to 2$$$ (of length 3). However, it would be wrong answer as you're asked to use the minimal possible number of operations, which is 1 in that case.

In the second example, it's possible to the sort the array with two cycles of total length 4 ($$$1 \to 2 \to 1$$$ and $$$3 \to 4 \to 3$$$). However, it's impossible to achieve the same using shorter cycles, which is required by $$$s=3$$$.

In the third example, the array is already sorted, so no operations are needed. Total length of empty set of cycles is considered to be zero.

Example input:
5 5
3 2 3 1 1

Example output:
1
5
1 4 2 3 5

Example input:
4 3
2 1 4 3

Example output:
-1

Editorial:
Let's solve an array if $$$a$$$ is permutation and the sum of cycle sizes is unlimited.
It's known that each permutation is composition of some non-intersecting cycles. If permutation is sorted answer is $$$0$$$. If permutation is $$$1$$$ cycle and some fixed indexes answer is $$$1$$$, you should take this cycle to get this answer. If permutation is composition of $$$\geq 2$$$ cycles answer should be $$$\geq 2$$$, because it's impossible to use $$$1$$$ cycle. In this case it's possible to make the answer with $$$2$$$ cycles. Let's define inversed permutation for our permutation as composition of this cycles $$$(p_{{1}{1}} \to p_{{1}{2}} \to \dots \to p_{{1}{k_1}} \to p_{{1}{1}}), \dots, (p_{{m}{1}} \to p_{{m}{2}} \to \dots \to p_{{m}{k_m}} \to p_{{m}{1}})$$$ (all cycles, except cycles with length $$$1$$$). We can sort permutations using this $$$2$$$ cycles: $$$(p_{{1}{1}} \to p_{{1}{2}} \to \dots \to p_{{1}{k_1}} \to p_{{2}{1}} \to \dots \to p_{{m}{1}} \to p_{{m}{2}} \to \dots \to p_{{m}{k_m}} \to p_{{1}{1}})$$$ (all cycles, written in a row) and $$$(p_{{m}{1}} \to p_{{m-1}{1}} \to \dots p_{{1}{1}} \to p_{{m}{1}})$$$ (first elements of cycles in inversed order). This solution used sum of cycle sizes $$$t+m$$$, there $$$t$$$ — number of non-fixed elements and $$$m$$$ — number of cycles with size $$$1$$$.
Now let's solve problem for permutation, if we can use sum of cycle sizes $$$\leq s$$$. Each solution should use sum of cycle sizes $$$\geq t$$$, because we should shift each non-fixed element. So if $$$s < t$$$ answer is $$$-1$$$. Let's call each cycle from $$$m$$$ cycles bad, if each of it's element shifted exactly $$$1$$$ time in the answer. It can be proved, that each bad cycle should be used in the answer. Let's define $$$x$$$ as number of bad cycles and $$$y$$$ number of other cycles. So $$$x+y=m$$$. Sum of cycles in the answer $$$\geq t+y$$$. So, $$$t+y \leq s$$$ ==> $$$y \leq s-t$$$ ==> $$$x=m-y \geq m+t-s$$$. Number of cycles in the answer $$$\geq x + min(y, 2)$$$. It's true, because each of $$$x$$$ bad cycles are in answer and other $$$y$$$ cycles can be sorted using $$$\geq min(y, 2)$$$ cycles. We should take $$$x$$$ as maximal as possible, because if we increase $$$x$$$ by $$$1$$$ sum $$$min(y, 2) + x$$$ won't increase. Minimal $$$x$$$, that we can use is $$$max(0, m+t-s)$$$. So we get $$$y=m-max(0,m+t-s)=m+min(s-t-m, 0)=min(s-t, 0)=s-t$$$ (because $$$s \geq t$$$). So answer in this case if $$$max(0, m+t-s)+min(s-t, 2)$$$. We can build it, if we use $$$x=max(0, m+t-s)$$$ any of $$$m$$$ cycles, and for other $$$y=s-t$$$ cycles do same construction as in previous case.
Let's solve problem for array. Let's define $$$b$$$ as sorted array $$$a$$$ and $$$t$$$ as count of $$$1 \leq i \leq n$$$, such that $$$a_i \neq b_i$$$. Our solution will sort some permutation $$$p$$$, such that $$$a_{p_i} = b_i$$$, for all $$$i$$$. Answer for permutation is $$$max(0, m+t-s)+min(s-t, 2)$$$. In this formula $$$s$$$ и $$$t$$$ fixed. So to minimize the answer we should minimize $$$m$$$. So we should sort array using array with as minumal as possible number of cycles. To do it let's build directed graph: vertexes is number in array, let's add edge from $$$a_i$$$ to $$$b_i$$$ for all $$$i$$$, such that $$$a_i \neq b_i$$$. It's easy to see, that we should take euler cycle in each component of this graph and build permutation with this cycles to make number of cycles in permutation as minimal as possible.
To code this solution without building graph let's take first any sorting permutation. After that, we can merge cycles. If $$$a_i = a_j$$$ and $$$i$$$ and $$$j$$$ in different cycles of permutation, we can merge this cycles using $$$swap(p_i, p_j)$$$. So let's merge all possible cycles using DSU for components.
Time complexity: $$$O(n * log(n))$$$.