CF1553E.Permutation Shift

An identity permutation of length $n$ is an array $[1, 2, 3, \dots, n]$.

We performed the following operations to an identity permutation of length $n$:

• firstly, we cyclically shifted it to the right by $k$ positions, where $k$ is unknown to you (the only thing you know is that $0 \le k \le n - 1$). When an array is cyclically shifted to the right by $k$ positions, the resulting array is formed by taking $k$ last elements of the original array (without changing their relative order), and then appending $n - k$ first elements to the right of them (without changing relative order of the first $n - k$ elements as well). For example, if we cyclically shift the identity permutation of length $6$ by $2$ positions, we get the array $[5, 6, 1, 2, 3, 4]$;
• secondly, we performed the following operation at most $m$ times: pick any two elements of the array and swap them.

You are given the values of $n$ and $m$, and the resulting array. Your task is to find all possible values of $k$ in the cyclic shift operation.

长度为 $n$ 的恒等排列是一个数组 $[1, 2, 3, \dots, n]$。

我们对长度为 $n$ 的恒等排列执行了以下操作：

• 首先，将其向右循环移动 $k$ 个位置，其中 $k$ 是未知的（你唯一知道的是 $0 \le k \le n - 1$）。当一个数组向右循环移动 $k$ 个位置时，所得数组由原数组的最后 $k$ 个元素（不改变它们的相对顺序）构成前缀，再将原数组的前 $n - k$ 个元素（同样不改变这 $n - k$ 个元素之间的相对顺序）作为后缀拼接而成。例如，若将长度为 $6$ 的恒等排列向右循环移动 $2$ 个位置，则得到数组 $[5, 6, 1, 2, 3, 4]$；
• 其次，我们最多执行了 $m$ 次如下操作：任选数组中两个元素并交换它们。

你将获得 $n$、$m$ 的值以及最终得到的数组。你的任务是找出循环移动操作中所有可能的 $k$ 值。

The first line contains one integer $t$ ($1 \le t \le 10^5$) — the number of test cases.

Each test case consists of two lines. The first line contains two integers $n$ and $m$ ($3 \le n \le 3 \cdot 10^5$; $0 \le m \le \frac{n}{3}$).

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, each integer from $1$ to $n$ appears in this sequence exactly once) — the resulting array.

The sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^5$）—— 测试用例的数量。

每个测试用例由两行组成。第一行包含两个整数 $n$ 和 $m$（$3 \le n \le 3 \cdot 10^5$；$0 \le m \le \frac{n}{3}$）。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$，且 $1$ 到 $n$ 中的每个整数在此序列中恰好出现一次）—— 所得数组。

所有测试用例的 $n$ 值之和不超过 $3 \cdot 10^5$。

For each test case, print the answer in the following way:

• firstly, print one integer $r$ ($0 \le r \le n$) — the number of possible values of $k$ for the cyclic shift operation;
• secondly, print $r$ integers $k_1, k_2, \dots, k_r$ ($0 \le k_i \le n - 1$) — all possible values of $k$ in increasing order.

对于每个测试用例，按以下方式输出答案：

• 首先，输出一个整数 $r$（$0 \le r \le n$）—— 表示循环移位操作中可能的 $k$ 值的个数；
• 然后，输出 $r$ 个整数 $k_1, k_2, \dots, k_r$（$0 \le k_i \le n - 1$）—— 所有可能的 $k$ 值，按升序排列。

Consider the example:

• in the first test case, the only possible value for the cyclic shift is $3$. If we shift $[1, 2, 3, 4]$ by $3$ positions, we get $[2, 3, 4, 1]$. Then we can swap the $3$-rd and the $4$-th elements to get the array $[2, 3, 1, 4]$;
• in the second test case, the only possible value for the cyclic shift is $0$. If we shift $[1, 2, 3]$ by $0$ positions, we get $[1, 2, 3]$. Then we don't change the array at all (we stated that we made at most $1$ swap), so the resulting array stays $[1, 2, 3]$;
• in the third test case, all values from $0$ to $2$ are possible for the cyclic shift:
  • if we shift $[1, 2, 3]$ by $0$ positions, we get $[1, 2, 3]$. Then we can swap the $1$-st and the $3$-rd elements to get $[3, 2, 1]$;
  • if we shift $[1, 2, 3]$ by $1$ position, we get $[3, 1, 2]$. Then we can swap the $2$-nd and the $3$-rd elements to get $[3, 2, 1]$;
  • if we shift $[1, 2, 3]$ by $2$ positions, we get $[2, 3, 1]$. Then we can swap the $1$-st and the $2$-nd elements to get $[3, 2, 1]$;
• in the fourth test case, we stated that we didn't do any swaps after the cyclic shift, but no value of cyclic shift could produce the array $[1, 2, 3, 4, 6, 5]$.

考虑以下示例：

• 在第一个测试用例中，循环移位的唯一可能值为 $3$。若将数组 $[1, 2, 3, 4]$ 向右循环移位 $3$ 个位置，得到 $[2, 3, 4, 1]$；然后交换第 $3$ 个与第 $4$ 个元素，即可得到数组 $[2, 3, 1, 4]$；
• 在第二个测试用例中，循环移位的唯一可能值为 $0$。若将数组 $[1, 2, 3]$ 向右循环移位 $0$ 个位置，得到 $[1, 2, 3]$；此时我们完全不进行交换（题目说明最多执行 $1$ 次交换），因此最终数组仍为 $[1, 2, 3]$；
• 在第三个测试用例中，循环移位的所有可能值为 $0$ 到 $2$：
  • 若将数组 $[1, 2, 3]$ 向右循环移位 $0$ 个位置，得到 $[1, 2, 3]$；然后交换第 $1$ 个与第 $3$ 个元素，得到 $[3, 2, 1]$；
  • 若将数组 $[1, 2, 3]$ 向右循环移位 $1$ 个位置，得到 $[3, 1, 2]$；然后交换第 $2$ 个与第 $3$ 个元素，得到 $[3, 2, 1]$；
  • 若将数组 $[1, 2, 3]$ 向右循环移位 $2$ 个位置，得到 $[2, 3, 1]$；然后交换第 $1$ 个与第 $2$ 个元素，得到 $[3, 2, 1]$；
• 在第四个测试用例中，题目声明在循环移位后未执行任何交换操作，但不存在任何循环移位值能够将原数组变为 $[1, 2, 3, 4, 6, 5]$。