{"problem":{"name":"E. Cycle sort","description":{"content":"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1012E"},"statements":[{"statement_type":"Markdown","content":"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$.\n\nFor 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$.\n\nYour 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.\n\n## Input\n\nThe 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.\n\nThe next line contains $n$ integers $a_1, a_2, \\dots, a_n$—elements of the array ($1 \\leq a_i \\leq 10^9$).\n\n## Output\n\nIf it's impossible to sort the array using cycles of total length not exceeding $s$, print a single number \"_\\-1_\" (quotes for clarity).\n\nOtherwise, print a single number $q$— the minimum number of operations required to sort the array.\n\nOn 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.\n\nThe 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.\n\nIf there are several possible answers with the optimal $q$, print any of them.\n\n[samples]\n\n## Note\n\nIn 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.\n\nIn 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$.\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你被给定一个包含 $n$ 个正整数的数组 $a_1, a_2, dots.h, a_n$。你可以任意次执行以下操作：选择若干个互不相同的下标 $i_1, i_2, dots.h, i_k$（$1 lt.eq i_j lt.eq n$），并将位置 $i_1$ 上的数移动到位置 $i_2$，位置 $i_2$ 上的数移动到位置 $i_3$，……，位置 $i_k$ 上的数移动到位置 $i_1$。换句话说，该操作对元素进行循环移位：$i_1 arrow.r i_2 arrow.r dots.h i_k arrow.r i_1$。\n\n例如，若 $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$。\n\n你的目标是使用最少的操作次数将数组变为非递减有序。附加约束是：所有操作中循环长度的总和不得超过一个给定数 $s$。如果在满足该约束的前提下无法对数组排序，你的解法也应报告这一点。\n\n输入的第一行包含两个整数 $n$ 和 $s$（$1 lt.eq n lt.eq 200 thin 000$, $0 lt.eq s lt.eq 200 thin 000$）——数组元素个数和循环长度总和的上限。\n\n第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$——数组元素（$1 lt.eq a_i lt.eq 10^9$）。\n\n如果无法使用总长度不超过 $s$ 的循环对数组排序，请输出单个数字 \"_-1_\"（引号仅用于清晰说明）。\n\n否则，输出单个数字 $q$——将数组排序所需的最少操作次数。\n\n接下来的 $2 dot.op q$ 行按应用顺序描述每个操作。第 $i$ 个操作的描述以一行开始，包含一个整数 $k$（$1 lt.eq k lt.eq n$）——循环的长度（即所选下标个数）。下一行应包含 $k$ 个互不相同的整数 $i_1, i_2, dots.h, i_k$（$1 lt.eq i_j lt.eq n$）——循环的下标。\n\n这些循环的长度总和应不超过 $s$，且在应用这 $q$ 次操作后数组应为有序。\n\n如果存在多个满足最优 $q$ 的答案，请输出任意一个。\n\n在第一个例子中，也可以用两次操作（总长度为 5）对数组排序：先应用循环 $1 arrow.r 4 arrow.r 1$（长度为 2），再应用循环 $2 arrow.r 3 arrow.r 5 arrow.r 2$（长度为 3）。但这是错误答案，因为题目要求使用最少的操作次数，该情况下最少为 1 次。\n\n在第二个例子中，可以用两个循环（总长度为 4：$1 arrow.r 2 arrow.r 1$ 和 $3 arrow.r 4 arrow.r 3$）对数组排序。但无法使用长度总和不超过 $s = 3$ 的更短循环达成相同效果。\n\n在第三个例子中，数组已有序，因此无需任何操作。空循环集合的总长度视为 0。\n\n## Input\n\n输入的第一行包含两个整数 $n$ 和 $s$（$1 lt.eq n lt.eq 200 thin 000$, $0 lt.eq s lt.eq 200 thin 000$）——数组元素个数和循环长度总和的上限。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$——数组元素（$1 lt.eq a_i lt.eq 10^9$）。\n\n## Output\n\n如果无法使用总长度不超过 $s$ 的循环对数组排序，请输出单个数字 \"_-1_\"（引号仅用于清晰说明）。否则，输出单个数字 $q$——将数组排序所需的最少操作次数。接下来的 $2 dot.op q$ 行按应用顺序描述每个操作。第 $i$ 个操作的描述以一行开始，包含一个整数 $k$（$1 lt.eq k lt.eq n$）——循环的长度（即所选下标个数）。下一行应包含 $k$ 个互不相同的整数 $i_1, i_2, dots.h, i_k$（$1 lt.eq i_j lt.eq n$）——循环的下标。这些循环的长度总和应不超过 $s$，且在应用这 $q$ 次操作后数组应为有序。如果存在多个满足最优 $q$ 的答案，请输出任意一个。\n\n[samples]\n\n## Note\n\n在第一个例子中，也可以用两次操作（总长度为 5）对数组排序：先应用循环 $1 arrow.r 4 arrow.r 1$（长度为 2），再应用循环 $2 arrow.r 3 arrow.r 5 arrow.r 2$（长度为 3）。但这是错误答案，因为题目要求使用最少的操作次数，该情况下最少为 1 次。在第二个例子中，可以用两个循环（总长度为 4：$1 arrow.r 2 arrow.r 1$ 和 $3 arrow.r 4 arrow.r 3$）对数组排序。但无法使用长度总和不超过 $s = 3$ 的更短循环达成相同效果。在第三个例子中，数组已有序，因此无需任何操作。空循环集合的总长度视为 0。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, s \\in \\mathbb{Z} $ with $ 1 \\le n \\le 200{,}000 $, $ 0 \\le s \\le 200{,}000 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers.  \nLet $ B = (b_1, b_2, \\dots, b_n) $ be the sorted version of $ A $ in non-decreasing order.  \n\nDefine a permutation $ \\pi \\in S_n $ such that for each position $ i \\in \\{1, \\dots, n\\} $, the element $ a_i $ should move to position $ \\pi(i) $ in the sorted array, i.e., $ a_i = b_{\\pi(i)} $.  \nAssume indices are 1-based.  \n\nA *cycle operation* is a cyclic permutation of a subset of indices $ \\{i_1, i_2, \\dots, i_k\\} $, where $ k \\ge 1 $, such that:  \n$ i_1 \\mapsto i_2, i_2 \\mapsto i_3, \\dots, i_k \\mapsto i_1 $.  \n\n**Constraints**  \n1. The total sum of lengths of all applied cycle operations must satisfy $ \\sum \\text{len}(C_j) \\le s $.  \n2. After applying all operations, the array must equal $ B $.  \n3. Each cycle operation must act on distinct indices and correspond to a cycle in the permutation $ \\pi $.  \n\n**Objective**  \nFind the minimum number $ q $ of cycle operations such that:  \n- The composition of these cycles equals $ \\pi $,  \n- The sum of the lengths of the cycles is $ \\le s $.  \n\nIf no such sequence of cycles exists, output $-1$.  \nOtherwise, output $ q $, followed by $ q $ cycle descriptions (each: length $ k $, then $ k $ indices).  \n\n**Note**: The minimal number of operations $ q $ is equal to the number of cycles in the cycle decomposition of $ \\pi $, excluding fixed points (cycles of length 1).  \nAny cycle of length $ k \\ge 2 $ must be applied as a single operation of length $ k $.  \nFixed points (cycles of length 1) require no operation.  \n\nThus, the total cycle length sum is $ \\sum_{C \\in \\text{cycles of } \\pi, |C| \\ge 2} |C| $.  \nIf this sum exceeds $ s $, output $-1$.  \nOtherwise, output $ q = \\#\\{C \\in \\text{cycles of } \\pi : |C| \\ge 2\\} $, followed by the cycles.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1012E","tags":["dsu","math"],"sample_group":[["5 5\n3 2 3 1 1","1\n5\n1 4 2 3 5"],["4 3\n2 1 4 3","\\-1"],["2 0\n2 2","0"]],"created_at":"2026-03-03 11:00:39"}}