Permutation Shift
Contest: Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 2100
Tags: brute force, combinatorics, constructive algorithms, dfs and similar, dsu, graphs, math

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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]$$$.

Example input:
4
4 1
2 3 1 4
3 1
1 2 3
3 1
3 2 1
6 0
1 2 3 4 6 5

Example output:
1 3
1 0
3 0 1 2
0

Editorial:
Let's decrease all numbers by $$$1$$$ and start the numeration from $$$0$$$, because cyclic shifts are very easy to describe this way. Let's observe for $$$n = 4$$$:
• $$$k = 0$$$. $$$p = [0, 1, 2, 3]$$$. So, $$$p_i = i$$$.
• $$$k = 1$$$. $$$p = [3, 0, 1, 2]$$$. So, $$$p_i = (i-1) \bmod n$$$.
• ...
Continuing this process, we verify that indeed, $$$p_i = (i-k) \bmod n$$$. Very simple!
Now suppose we have some value $$$0 \le k \le n - 1$$$ and we want to check if it is possible to obtain $$$p$$$ from $$$k$$$-th cyclic shift by doing at most $$$m$$$ swaps. For this, we can calculate the minimum number of swaps and check it is not more than $$$m$$$.
So, how to calculate the minimum number of swaps needed to transform a permutation $$$a$$$ to another permutation $$$b$$$? This is actually a well-known problem. The idea is, we build a graph with undirected edges $$$(a_i, b_i)$$$. The minimum number of swaps will be equal to $$$n - c$$$, where $$$c$$$ is equal to the number of connected components in the resulting graph.
Nice, now we can check if some $$$k$$$ is good in $$$O(n)$$$ time. But we can't check all of them, right? Here comes the crucial observation:
Suppose you get a permutation $$$a$$$ after a cyclic shift. Then you make at most $$$m$$$ swaps and obtain $$$b$$$. This means at most $$$2 \cdot m$$$ numbers will be out of order! That is, there will be at least $$$n - 2 \cdot m$$$ indices $$$i$$$ such that $$$a_i = b_i$$$.
So can we calculate the number $$$cnt_k$$$ — the count of integers in position for each cyclic shift $$$k$$$? Yes, we can! For an arbitrary $$$i$$$, there is exactly one $$$k$$$ such that $$$p_i = (i-k) \bmod n$$$.
But wait, it means there are in total only $$$n$$$ good positions because $$$\sum cnt_i = n$$$! And we check only those $$$k$$$ for which it is true that $$$cnt_k \ge n - 2 \cdot m$$$. Remember that weird constraint $$$m \le \frac{n}{3}$$$? Well, turns out there are at most $$$\frac{n}{n - \frac{2n}{3}} = 3$$$ different $$$k$$$ to consider!
So we know we check at most $$$3$$$ different values and we know how to check in $$$O(n)$$$ time. That concludes the solution. The time and space complexities are $$$O(n)$$$.