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.

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 $ .

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.

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