Problem Description

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

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

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

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

Your task is to sort the entire sequence in non-decreasing order using the minimum number of operations. Note that the total number of indices selected across all operations must not exceed $s$. If no such method exists (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 -1.

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

The next $2 \times q$ lines describe each operation.

For each operation, first output an integer $k$ indicating the number of indices selected in this operation, followed by a line containing $k$ integers $i_{1 \cdots k}$.

In the case of the minimum number of operations $q$, you can output any valid solution.

Sample Input and Output

Sample Input #1

5 5
3 2 3 1 1

Sample Output #1

1
5
1 4 2 3 5

Sample Input #2

4 3
2 1 4 3

Sample Output #2

-1

Sample Input #3

2 0
2 2

Sample Output #3

0

Sample Input #4

6 9
6 5 4 3 2 1

Sample Output #4

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

Sample Input #5

6 8
6 5 4 3 2 1

Sample Output #5

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

Notes

Sample 1 Explanation:

You can sort the array with two operations $1 \rightarrow 4 \rightarrow 1$ and $2 \rightarrow 3 \rightarrow 5 \rightarrow 2$, but this would be incorrect as your task is to minimize $q$, and the optimal solution has $q=1$.

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

Sample 2 Explanation:

The minimum total number of indices selected across all operations is $4$ (a feasible method is $1 \rightarrow 2 \rightarrow 1$ and $3 \rightarrow 4 \rightarrow 3$), thus there is no solution.

Sample 3 Explanation:

The array is already sorted, so no operations are needed.

Additional Notes:

Samples 4 and 5 meet the constraints of Subtasks 6 and 7.

Data Range:

For $100\%$ of the data: $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: Translation from LOJ

见题面 Input 部分

见题面 Output 部分