题目描述

给定一个长为 $n$ 的数列 $\{a_i\}$ ，你可以多次进行如下操作：

选定 $k$ 个不同的下标 $i_1,i_2\cdots,i_k$（其中 $1\leq i_j\leq n$），然后将 $a_{i_1}$ 移动到下标 $i_2$ 处，将 $a_{i_2}$ 移动到下标 $i_3$ 处，……，将 $a_{i_{k-1}}$ 移动到下标 $i_k$ 处，将 $a_{i_k}$ 移动到下标 $i_1$ 处。

换言之，你可以按照如下的顺序轮换元素：$i_1\rightarrow i_2\rightarrow\cdots\rightarrow i_{k}\rightarrow i_1$。

例如：$n=4,\{a_i\}=\{10,20,30,40\},i_1=2,i_2=3,i_3=4$ ，则操作完成后的 $a$ 数列变为 $\{10,40,20,30\}$。

你的任务是用操作次数最少的方法将整个数列排序成不降的。注意，所有操作中选定下标的个数总和不得超过 $s$ 。如果不存在这样的方法（无解），输出 -1。

输入格式

第一行，两个整数，$n$ 和 $s$。

第二行，$n$ 个整数 $a_{1\cdots n}$，表示数列 $\{a_i\}$。

输出格式

如果无解，仅输出 -1。

否则，第一行输出一个整数 $q$（可以为 $0$ ，参见样例 3 ），表示最少需要进行的操作次数。

接下来 $2\times q$ 行描述每次操作。

对于每次操作，先输出一个整数 $k$ 表示此操作选定的下标数量，然后在下一行中输出 $k$ 个整数 $i_{1\cdots k}$。

在操作次数 $q$ 最少的情况下，你可以输出任意一种可行方案。

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

提示

【样例一解释】

你可以用两次操作 $1\rightarrow 4\rightarrow 1$ 和 $2\rightarrow 3\rightarrow 5\rightarrow 2$ 排序数组，但这样会 WA，因为你的任务是最小化 $q$ ，而最优解的 $q=1$。

一种可行的方法是 $1\rightarrow 4\rightarrow 2\rightarrow 3\rightarrow 5\rightarrow 1$，即样例输出。

【样例二解释】

所有操作中选定下标的个数总和的最小值为 $4$（一种可行的方法是 $1\rightarrow 2\rightarrow 1$ 和 $3\rightarrow 4\rightarrow 3$），因此无解。

【样例三解释】

数组已经有序，因此不需要进行操作。

补充说明：样例 4 和 5 满足子任务 6 和 7 的限制。

---

【数据范围】

对于 $100\%$ 的数据：$1\leq n\leq 2\times 10^5$，$0\leq s\leq 2\times 10^5$，$1\leq a_i\leq 10^9$。

子任务编号	分数	限制
$1$	$0$	样例
$2$	$5$	$n,s\leq 2 且 1\leq a_i\leq 2$
$3$		$n\leq 5$
$4$		$1\leq a_i\leq 2$
$5$	$10$	$a 是个排列，s=2\times n$
$6$		$a 是个排列，n\leq 10^3$
$7$	$15$	$a 是个排列$
$8$		$s=2\times n$
$9$		$n\leq 10^3$
$10$	$20$	无特殊限制

---

来源：eJOI2018 Problem F「Cycle Sort」

说明：翻译来自 LOJ