CF1012E Cycle sort

给定一个长度为 $n$ 的正整数数组 $a_1, a_2, \dots, a_n$。你可以进行如下操作任意次：选择若干个不同的下标 $i_1, i_2, \dots, i_k$（$1 \le i_j \le n$），将位置 $i_1$ 上的数移动到位置 $i_2$，位置 $i_2$ 上的数移动到位置 $i_3$，……，位置 $i_k$ 上的数移动到位置 $i_1$。换句话说，该操作会对选中的元素进行循环移动：$i_1 \to i_2 \to \ldots \to i_k \to i_1$。 例如，若 $n=4$，数组为 $a_1=10, a_2=20, a_3=30, a_4=40$，选择三个下标 $i_1=2$，$i_2=1$，$i_3=4$，则操作后数组变为 $a_1=20, a_2=40, a_3=30, a_4=10$。 你的目标是通过最少次数的操作，使数组变为非递减有序。同时有一个额外限制：所有操作中循环长度之和不能超过 $s$。如果无法在该限制下将数组排序，需要输出无法完成的结果。

输入的第一行包含两个整数 $n$ 和 $s$（$1 \leq n \leq 200\,000$，$0 \leq s \leq 200\,000$）——数组的长度和循环长度之和的上限。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$——数组的元素（$1 \leq a_i \leq 10^9$）。

如果无法在循环长度之和不超过 $s$ 的条件下将数组排序，输出一行“-1”。 否则，输出一个整数 $q$——将数组排序所需的最少操作次数。 接下来 $2 \cdot q$ 行，依次描述每次操作。第 $i$ 次操作的描述包括一行一个整数 $k$（$1 \le k \le n$），表示本次循环的长度；下一行包含 $k$ 个不同的整数 $i_1, i_2, \dots, i_k$（$1 \le i_j \le n$），表示本次循环涉及的下标。 所有操作的循环长度之和不超过 $s$，且所有 $q$ 次操作后数组应为非递减有序。 如果存在多个最优 $q$ 的方案，输出任意一种即可。

在第一个样例中，也可以用两次操作、总长度为 5 的方案排序：先用循环 $1 \to 4 \to 1$（长度为 2），再用循环 $2 \to 3 \to 5 \to 2$（长度为 3）。但这不是最优方案，因为题目要求操作次数最少，在该情况下最优方案只需一次操作。 在第二个样例中，可以用两次循环、总长度为 4（$1 \to 2 \to 1$ 和 $3 \to 4 \to 3$）完成排序。但无法用更短的循环长度完成排序，而本题要求 $s=3$，因此无法完成。 在第三个样例中，数组已经有序，因此不需要任何操作。空操作集的总循环长度视为 0。 由 ChatGPT 4.1 翻译