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

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

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.


-----Examples-----

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
Output
1 3
1 0
3 0 1 2
0


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

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms

Combinatorics

Complete search

Mathematics

Spanning trees
Skill types: Complete search

Starter code:

Solutions:
import sys
input = sys.stdin.readline

class UnionFindAlgo:

	def __init__(self, n):
		self.par = [i for i in range(n)]

	def find(self, node):
		if self.par[node] == node:
			return node
		self.par[node] = self.find(self.par[node])
		return self.par[node]

	def union(self, u, v):
		a = self.find(u)
		b = self.find(v)
		if a == b:
			return
		self.par[b] = a
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	cnt = [0] * n
	for i in range(n):
		cnt[(i + 1 - p[i] + n) % n] += 1
	ans = []
	for i in range(n):
		if cnt[i] + 2 * m >= n:
			obj = UnionFindAlgo(n)
			curr = 0
			for j in range(i, n):
				obj.union(curr, p[j] - 1)
				curr += 1
			for j in range(0, i):
				obj.union(curr, p[j] - 1)
				curr += 1
			connectedRoot = set()
			for j in range(n):
				connectedRoot.add(obj.find(j))
			if n - len(connectedRoot) <= m:
				ans.append(i)
	print(len(ans), *ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	c = [0] * n
	for i in range(n):
		c[(i + 1 - p[i]) % n] += 1
	res = []
	for i in range(n):
		if c[i] >= n - 2 * m:
			swaps = 0
			norm = [0] * n
			rev_map = [0] * n
			for j in range(n):
				norm[j] = (p[j] + i - 1) % n
				rev_map[norm[j]] = j
			for j in range(n):
				if norm[j] != j:
					k = norm[j]
					ind_j = rev_map[j]
					(norm[ind_j], norm[j]) = (k, j)
					(rev_map[k], rev_map[j]) = (ind_j, j)
					swaps += 1
			if swaps <= m:
				res.append(i)
	print(len(res), *res)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
q = int(input())
from collections import deque

def bfs(graph, currnode, visited):
	stack = deque()
	stack.append(currnode)
	while stack:
		currnode = stack.popleft()
		if visited[currnode] == False:
			visited[currnode] = True
		for neigbour in graph[currnode]:
			if visited[neigbour] == False:
				visited[neigbour] = True
				stack.append(neigbour)
	return ans

def find_minswaps(a, b):
	graph = {}
	for i in range(len(a)):
		if a[i] == b[i]:
			graph[a[i]] = []
		if a[i] not in graph:
			graph[a[i]] = [b[i]]
		else:
			graph[a[i]].append(b[i])
		if b[i] not in graph:
			graph[b[i]] = [a[i]]
		else:
			graph[b[i]].append(a[i])
	visited = [False for x in range(n)]
	count = 0
	for i in range(n):
		if visited[i] == False:
			count += 1
			bfs(graph, i, visited)
	return count
while q:
	q -= 1
	(n, m) = [int(x) for x in input().split()]
	arr = [int(x) - 1 for x in input().split()]
	k = [0 for x in range(n)]
	for i in range(n):
		x = arr[i]
		y = arr[i] - n
		if i - x >= 0:
			k[i - x] += 1
		else:
			k[i - y] += 1
	tocheck = []
	for i in range(n):
		if k[i] >= n - 2 * m:
			tocheck.append(i)
	ans = []
	while tocheck:
		k = tocheck.pop()
		a = [(i - k) % n for i in range(n)]
		s = n - find_minswaps(a, arr)
		if s <= m:
			ans.append(k)
	ans.sort()
	sys.stdout.write(str(len(ans)) + ' ')
	for i in range(len(ans) - 1):
		sys.stdout.write(str(ans[i]) + ' ')
	if ans:
		sys.stdout.write(str(ans[-1]) + '\n')
	else:
		sys.stdout.write('\n')


from __future__ import print_function
import math
from collections import deque
import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())

def bfs(d, i):
	queue = deque()
	queue.append(i + 1)
	while queue:
		s = queue.popleft()
		v[s - 1] = 1
		for i in d[s]:
			if not v[i - 1]:
				queue.append(i)
				v[i - 1] = 1

def f(k, n):
	a = [n - k + i + 1 for i in range(k)]
	a.extend([i + 1 for i in range(n - k)])
	d = {}
	for i in range(n):
		d[i + 1] = []
	for i in range(n):
		if l[i] != a[i]:
			d[a[i]].append(l[i])
			d[l[i]].append(a[i])
	c = 0
	for i in range(n):
		if not v[i] and len(d[i + 1]) > 0:
			bfs(d, i)
			c += 1
	return c
for _ in range(inp()):
	(n, m) = invr()
	global l, v
	v = []
	l = inlt()
	out = [0] * n
	for i in range(n):
		ind = i + 1
		el = l[i]
		if ind >= el:
			di = ind - el
		else:
			di = n - (el - ind)
		out[di] += 1
	x = []
	for i in range(n):
		if out[i] >= n - 2 * m:
			v = [0] * n
			if n - out[i] - f(i, n) <= m:
				x.append(i)
	x.sort()
	print(len(x), end=' ')
	print(*x)


import sys
import math
input = sys.stdin.readline
imp = 'IMPOSSIBLE'
t = int(input())
for test in range(t):
	(n, m) = list(map(int, input().split(' ')))
	a = list(map(int, input().split(' ')))
	poc = [0 for i in range(n)]
	for i in range(n):
		kk = (i + 1 - a[i]) % n
		poc[kk] += 1
	moz = []
	for i in range(n):
		if poc[i] >= n - 2 * m:
			moz.append(i)
	ine = []
	res = []
	for mo in moz:
		ine = []
		for i in range(mo, n):
			if (i + 1 - a[i]) % n != mo:
				ine.append(a[i])
		for i in range(mo):
			if (i + 1 - a[i]) % n != mo:
				ine.append(a[i])
		sorine = sorted(enumerate(ine), key=lambda x: x[1])
		convine = [0 for i in range(len(ine))]
		for i in range(len(ine)):
			convine[sorine[i][0]] = i + 1
		jo = [0 for i in range(len(ine))]
		i = 0
		sets = 0
		while i < len(ine):
			if jo[i]:
				i += 1
			else:
				sets += 1
				k = i
				jo[k] = 1
				while convine[k] != i + 1:
					k = convine[k] - 1
					jo[k] = 1
				i += 1
		if len(ine) - sets <= m:
			res.append(str(mo))
	print(str(len(res)) + ' ' + ' '.join(res))


def naiveSolve():
	return

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		(n, m) = readIntArr()
		p = readIntArr()
		for i in range(n):
			p[i] -= 1
		kMatches = [0] * n
		for i in range(n):
			kMatches[(i - p[i] + n) % n] += 1
		matches = []
		minMatchCnt = n - 2 * m
		origPerm = list(range(n))
		for k in range(n):
			matchCnts = kMatches[k]
			if matchCnts >= minMatchCnt:
				arr = origPerm[n - k:] + origPerm[:n - k]
				targetMap = dict()
				for i in range(n):
					targetMap[arr[i]] = i
				adj = [-1] * n
				for i in range(n):
					adj[i] = targetMap[p[i]]
				visited = [False] * n
				groups = 0
				for i in range(n):
					if i == adj[i]:
						continue
					if visited[i]:
						continue
					groups += 1
					visited[i] = True
					node = adj[i]
					while visited[node] == False:
						visited[node] = True
						node = adj[node]
				misMatchCnts = n - matchCnts
				minMoves = misMatchCnts - groups
				if minMoves <= m:
					matches.append(k)
		ans = [len(matches)]
		ans.extend(matches)
		allans.append(ans)
	multiLineArrayOfArraysPrint(allans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(l, r):
	print('? {} {}'.format(l, r))
	sys.stdout.flush()
	return int(input())

def answerInteractive(x):
	print('! {}'.format(x))
	sys.stdout.flush()
inf = float('inf')
MOD = 998244353
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 999999999999999999999999
alphabets = 'abcdefghijklmnopqrstuvwxyz'

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class SegTree:

	def __init__(self, n):
		self.N = 1 << n.bit_length()
		self.tree = [0] * (self.N << 1)

	def update(self, i, j, v):
		i += self.N
		j += self.N
		while i <= j:
			if i % 2 == 1:
				self.tree[i] += v
			if j % 2 == 0:
				self.tree[j] += v
			(i, j) = (i + 1 >> 1, j - 1 >> 1)

	def query(self, i):
		v = 0
		i += self.N
		while i > 0:
			v += self.tree[i]
			i >>= 1
		return v

def SieveOfEratosthenes(limit):
	isPrime = [True] * (limit + 1)
	isPrime[0] = isPrime[1] = False
	primes = []
	for i in range(2, limit + 1):
		if not isPrime[i]:
			continue
		primes += [i]
		for j in range(i * i, limit + 1, i):
			isPrime[j] = False
	return primes

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')

	def valid_graph(b, n, m):
		graph = [[] for v in range(n + 1)]
		vis = [0] * (n + 1)
		for i in range(n):
			graph[a[i]].append(b[i])
			graph[b[i]].append(a[i])
		connected_components = 0

		def dfs(v):
			vis[v] = 1
			for u in graph[v]:
				if not vis[u]:
					dfs(u)
		for i in range(1, n + 1):
			if not vis[i]:
				connected_components += 1
				dfs(i)
		if n - connected_components <= m:
			return True
		return False
	tc = ri()
	for _ in range(tc):
		(n, m) = ria()
		a = ria()
		offsets = {}
		for pos in range(1, n + 1):
			offset = 0
			offset = (n + pos - a[pos - 1]) % n
			if offset in offsets:
				offsets[offset] += 1
			else:
				offsets[offset] = 1
		valid_frequency_offsets = []
		for offset in offsets:
			if offsets[offset] >= n // 3:
				valid_frequency_offsets.append(offset)
		valid_offsets = []
		for offset in valid_frequency_offsets:
			offset_permutation = [0] * n
			for i in range(1, n + 1):
				pos = (i + offset - 1) % n
				offset_permutation[pos] = i
			if valid_graph(offset_permutation, n, m):
				valid_offsets.append(offset)
		print(len(valid_offsets), *sorted(valid_offsets))
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def corr(num, k, n):
	if num > k:
		return num - k - 1
	else:
		return num + n - k - 1

def examine(arr, k, m):
	n = len(arr)
	visited = [False] * n
	tot = 0
	for i in range(n):
		visited[i] = True
		if corr(arr[i], k, n) == i:
			continue
		temp = 0
		j = corr(arr[i], k, n)
		while not visited[j]:
			visited[j] = True
			j = corr(arr[j], k, n)
			temp += 1
		tot += temp
	return tot <= m

def main(t):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	dic = {}
	for i in range(n):
		if arr[i] >= i + 1:
			diff = arr[i] - i - 1
		else:
			diff = arr[i] - 1 - i + n
		if diff not in dic:
			dic[diff] = 0
		dic[diff] += 1
	ans = []
	for key in dic:
		if dic[key] >= n - 2 * m:
			if examine(arr, key, m):
				if key == 0:
					ans.append(0)
				else:
					ans.append(n - key)
	ans = sorted(ans)
	ans.insert(0, len(ans))
	ans = ' '.join(map(str, ans))
	print(ans)
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1


from sys import stdin
t = int(stdin.readline())
for _ in range(t):
	(n, m) = map(int, stdin.readline().split())
	tpl = tuple(map(lambda x: int(x) - 1, stdin.readline().split()))
	cnv = dict(((tpl[i], i) for i in range(n)))
	dic = {}
	ans = []
	for i in range(n):
		diff = (tpl[i] - i) % n
		if diff not in dic:
			dic[diff] = 0
		dic[diff] += 1
	for key in dic:
		if dic[key] + 2 * m < n:
			continue
		count = 0
		s = set()
		for i in range(n):
			if i not in s:
				s.add(i)
				while cnv[(i + key) % n] not in s:
					i = cnv[(i + key) % n]
					count += 1
					s.add(i)
		if count <= m:
			ans.append((n - key) % n)
	print(len(ans), *sorted(ans))


from collections import Counter

def count_swaps(p, k):
	n = len(p)
	visited = [False] * n
	loops = 0
	for i in range(n):
		loops += not visited[i]
		while not visited[i]:
			visited[i] = True
			i = (p[i] + k - 1) % n
	return n - loops

def solve():
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	c = Counter(((i - pi) % n for (i, pi) in enumerate(p, start=1)))
	for (k, cnt) in c.most_common(3):
		if count_swaps(p, k) <= m:
			yield k
for __ in range(int(input())):
	arr = sorted(solve())
	print(len(arr), *arr)


import sys, os
from io import BytesIO, IOBase
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + end)

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True

def possible(ind, arr, m):
	reqd = 0
	n = len(arr)
	vis = l1d(n + 1)
	for i in range(n):
		if not vis[arr[i]]:
			x = arr[i]
			while (x - ind) % n != i:
				vis[x] = 1
				x = arr[(x - ind) % n]
				reqd += 1
				if reqd > m:
					return False
			vis[x] = 1
	return True
for _ in range(iinp()):
	(n, m) = mp()
	arr = lmp()
	cnt = dd(int)
	for i in range(n):
		cnt[(arr[i] - i + n - 1) % n + 1] += 1
	x = n - 2 * (n // 3)
	poss = [i for i in cnt.keys() if cnt[i] >= x]
	ansl = []
	for i in poss:
		if possible(i, arr, m):
			ansl.append((n + 1 - i) % n)
	ansl.sort()
	out(len(ansl), end=' ')
	outa(*ansl)


import sys
input = sys.stdin.readline

def get_root(s):
	v = []
	while not s == root[s]:
		v.append(s)
		s = root[s]
	for i in v:
		root[i] = s
	return s

def unite(s, t):
	(rs, rt) = (get_root(s), get_root(t))
	if not rs ^ rt:
		return
	if rank[s] == rank[t]:
		rank[rs] += 1
	if rank[s] >= rank[t]:
		root[rt] = rs
		size[rs] += size[rt]
	else:
		root[rs] = rt
		size[rt] += size[rs]
	return

def same(s, t):
	return True if get_root(s) == get_root(t) else False
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	ans = []
	l = n - 2 * m
	x = [0] * n
	for i in range(n):
		x[(i + 1 - p[i]) % n] += 1
	for k in range(n):
		if x[k] >= l:
			p0 = [(i - k) % n + 1 for i in range(n)]
			root = [i for i in range(n + 1)]
			rank = [1 for _ in range(n + 1)]
			size = [1 for _ in range(n + 1)]
			for i in range(n):
				unite(p[i], p0[i])
			cnt = [0] * (n + 1)
			for i in range(1, n + 1):
				cnt[get_root(i)] += 1
			m0 = 0
			for i in cnt:
				m0 += max(i - 1, 0)
			if m0 <= m:
				ans.append(k)
	ans = [len(ans)] + ans
	print(*ans)


import sys
import math
from collections import deque, Counter
int1 = lambda x: int(x) - 1
inp = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
mi1 = lambda : map(int1, input().split())
li1 = lambda : list(mi1())
mis = lambda : map(str, input().split())
lis = lambda : list(mis())
pr = print
from collections import defaultdict
mod = 10 ** 9 + 7
Mod = 998244353
INF = 10 ** 18
ans = 0
q = inp()
for _ in range(q):
	(n, m) = mi()
	a = li()
	c = [0] * n
	for i in range(n):
		c[(i + 1 - a[i]) % n] += 1
	ans = []
	for i in range(n):
		if c[i] >= n - 2 * m:
			b = [0] * n
			for j in range(n):
				b[j] = a[(i + j) % n] - 1
			cnt = 0
			seen = [True] * n
			for j in range(n):
				if b[j] == j:
					seen[j] = True
				elif seen[j]:
					cyc = 1
					seen[j] = False
					k = b[j]
					while j != k:
						cyc += 1
						seen[k] = False
						k = b[k]
					cnt += cyc - 1
			if cnt <= m:
				ans.append(i)
	print(len(ans), *ans)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def minSwaps(arr):
	n = len(arr)
	arrpos = [*enumerate(arr)]
	arrpos.sort(key=lambda it: it[1])
	vis = {k: False for k in range(n)}
	ans = 0
	for i in range(n):
		if vis[i] or arrpos[i][0] == i:
			continue
		cycle_size = 0
		j = i
		while not vis[j]:
			vis[j] = True
			j = arrpos[j][0]
			cycle_size += 1
		if cycle_size > 0:
			ans += cycle_size - 1
	return ans
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	cnt = [0] * (n + 1)
	for i in range(n):
		if i + 1 <= a[i]:
			cnt[a[i] - i - 1] += 1
		else:
			cnt[n - i - 1 + a[i]] += 1
	ans = []
	x = n - m * 2
	for i in range(len(cnt)):
		if cnt[i] >= x:
			na = a[n - i:] + a[:n - i]
			if minSwaps(na) <= m:
				ans.append(i)
	for i in range(len(ans)):
		if ans[i] > 0:
			ans[i] = n - ans[i]
	ans.sort()
	print(len(ans), *ans)


from io import BytesIO, IOBase
import sys
import math
import os
import heapq
from collections import defaultdict, deque
from math import ceil
from bisect import bisect_left, bisect_left
from time import perf_counter
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def mint():
	return map(int, input().split())

def mfloat():
	return map(float, input().split())

def intin():
	return int(input())

def moves(k, n, a):
	accounted = [False] * n
	ans = 0
	for i in range(n):
		if accounted[i]:
			continue
		shift = i + 1 - a[i]
		if shift < 0:
			shift += n
		if shift == k:
			continue
		start = i
		flag = 0
		while not accounted[start]:
			flag = 1
			index = (a[start] - 1 + k) % n
			accounted[start] = True
			ans += 1
			start = index
		ans -= flag
	return ans

def solve():
	(n, m) = map(int, input().split())
	shifts = [0] * n
	(*a,) = map(int, input().split())
	for (i, x) in enumerate(a):
		if x <= i + 1:
			shifts[i + 1 - x] += 1
		else:
			shifts[n - x + i + 1] += 1
	possible = [i for i in range(n) if shifts[i] >= n - 2 * m]
	ans = [i for i in possible if moves(i, n, a) <= m]
	print(len(ans), *ans)

def main():
	t = int(input())
	for _ in range(t):
		solve()
start_time = perf_counter()
main()
print(perf_counter() - start_time, file=sys.stderr)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	cnt = [0] * n
	for i in range(n):
		cnt[(i + 1 - p[i]) % n] += 1
	ans = []
	for i in range(n):
		if (n - cnt[i] + 1) // 2 > m:
			continue
		x = list(range(n - i + 1, n + 1)) + list(range(1, n - i + 1))
		x_idx = [-1] * (n + 1)
		for j in range(n):
			x_idx[x[j]] = j
		score = 0
		for j in range(n):
			if x[j] != p[j]:
				k = x_idx[p[j]]
				(x[j], x[k]) = (x[k], x[j])
				x_idx[x[j]] = j
				x_idx[x[k]] = k
				score += 1
		if score <= m:
			ans.append(i)
	print(len(ans), *ans)


import sys
input = sys.stdin.readline
from collections import Counter

class DSU:

	def __init__(self, n):
		self.uf = {i: i for i in range(n)}
		self.rank = {i: 1 for i in range(n)}
		self.cnt = n

	def find(self, x):
		if self.uf[x] != x:
			self.uf[x] = self.find(self.uf[x])
		return self.uf[x]

	def union(self, x, y):
		(px, py) = (self.find(x), self.find(y))
		if px != py:
			if self.rank[px] > self.rank[py]:
				(px, py) = (py, px)
			self.rank[py] += self.rank[px]
			self.uf[px] = py
			self.cnt -= 1
			return True
		return False
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	A = [a - 1 for a in A]
	B = [(i - a) % n for (i, a) in enumerate(A)]
	cnt = Counter(B)
	ans = []
	X = list(range(n))
	for k in range(n):
		if n - cnt[k] > 2 * m:
			continue
		seen = [0] * n
		cycle = 0
		cur = X[-k:] + X[:-k]
		dsu = DSU(n)
		for (a, b) in zip(A, cur):
			dsu.union(a, b)
		if n - dsu.cnt <= m:
			ans.append(k)
	print(len(ans), *ans)


from copy import deepcopy
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	cnt = {}
	for i in range(n):
		a[i] -= i + 1
		a[i] = (a[i] + n) % n
		if a[i] not in cnt:
			cnt[a[i]] = 0
		cnt[a[i]] += 1
	b = deepcopy(a)
	ans = []
	for k in cnt:
		if cnt[k] >= n - m * 2:
			a = deepcopy(b)
			res = 0
			for i in range(n):
				a[i] += -k
				a[i] = a[i] % n
			bj = [0] * (n + 1)
			for i in range(n):
				t = (i + a[i]) % n
				g = 0
				while bj[t] == 0:
					g = 1
					bj[t] = 1
					t = (a[t] + t) % n
				res += g
			if n - res <= m:
				ans.append(str((n - k) % n))
	ans.sort()
	print(len(ans), ' '.join(ans))


def solve(n, m, perm):
	cyc_right = [0] * n
	for (i, p) in enumerate(perm):
		k = (n + i + 1 - p) % n
		cyc_right[k] += 1
	check_these = []
	for (i, right) in enumerate(cyc_right):
		if right >= n - 2 * m:
			check_these.append(i)
	check_these.sort()
	check_copy = check_these[:]
	for k in check_copy:
		swaps = 0
		tmp_perm = perm[:]
		for (i, p) in enumerate(tmp_perm):
			if k != (n + i + 1 - p) % n:
				tmp = tmp_perm[i]
				while k != (n + i + 1 - tmp) % n:
					swap_index = (k + tmp) % n - 1
					tmp_perm[i] = tmp_perm[swap_index]
					tmp_perm[swap_index] = tmp
					tmp = tmp_perm[i]
					swaps += 1
				if swaps > m:
					check_these.remove(k)
					break
	return check_these
import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input().decode().strip())
for t in range(T):
	(n, m) = [int(x) for x in input().decode().strip().split(' ')]
	perm = [int(x) for x in input().decode().strip().split(' ')]
	res1 = solve(n, m, perm)
	if len(res1) == 0:
		print('0')
	else:
		res = str(len(res1)) + ' ' + ' '.join([str(x) for x in res1])
		print(res)


def ok(n, m, arr):
	used = [0] * n
	ans = 0
	for i in range(n):
		if used[i] == 0:
			j = i
			while used[j] == 0:
				used[j] = 1
				j = arr[j]
			ans += 1
	return n - ans <= m

def solve():
	(n, m) = map(int, input().split())
	arr = list(map(lambda x: int(x) - 1, input().split()))
	c = [0] * n
	for (i, a) in enumerate(arr):
		c[(i - a) % n] += 1
	ans = []
	for k in range(n):
		if c[k] >= n // 3 and ok(n, m, arr[k:] + arr[:k]):
			ans.append(k)
	print(len(ans), *ans)
import sys
input = lambda : sys.stdin.readline().rstrip()
t = int(input())
for i in range(t):
	solve()


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for tests in range(t):
	(n, m) = map(int, input().split())
	P = list(map(int, input().split()))
	Coincide = [0] * n
	for i in range(n):
		Coincide[(i + 1 - P[i]) % n] += 1
	ANS = []
	for kuru in range(n):
		if (n - Coincide[kuru] + 1) // 2 > m:
			continue
		X = list(range(n - kuru + 1, n + 1)) + list(range(1, n - kuru + 1))
		X_INV = [-1] * (n + 1)
		for i in range(n):
			X_INV[X[i]] = i
		score = 0
		for i in range(n):
			if X[i] != P[i]:
				k = X_INV[P[i]]
				(X[i], X[k]) = (X[k], X[i])
				X_INV[X[i]] = i
				X_INV[X[k]] = k
				score += 1
		if score <= m:
			ANS.append(kuru)
	print(len(ANS), *ANS)


import sys
IS_INTERACTIVE = False
input = input
if not IS_INTERACTIVE:
	(*data,) = sys.stdin.read().split('\n')[::-1]

	def input():
		return data.pop()

def fprint(*args, **kwargs):
	print(*args, **kwargs, flush=True)

def eprint(*args, **kwargs):
	print(*args, **kwargs, file=sys.stderr)

def check(arr, k, m):
	arr = arr[k:] + arr[:k]
	solved = [0] * len(arr)
	cnt = 0
	for i in range(len(arr)):
		if not solved[i] and i != arr[i]:
			length = 1
			cur = arr[i]
			solved[cur] = 1
			while cur != i:
				length += 1
				cur = arr[cur]
				solved[cur] = 1
			cnt += max(0, length - 1)
	return cnt <= m
supans = []
for i in range(int(input())):
	(n, m) = map(int, input().split())
	(*arr,) = map(int, input().split())
	arr = [v - 1 for v in arr]
	shifts = [0] * n
	for (i, v) in enumerate(arr):
		shifts[(i - v) % n] += 1
	ans = []
	for k in range(n):
		if shifts[k] >= n - 2 * m:
			if check(arr, k, m):
				ans.append(k)
	fmt = '%s %s' % (len(ans), ' '.join(map(str, ans)))
	supans.append(fmt)
print('\n'.join(supans))


import time
import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string, heapq as h
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
	return int(input())

def getStrs():
	return input().split()

def getInts():
	return list(map(int, input().split()))

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def getBin():
	return list(map(int, list(input())))

def isInt(s):
	return '0' <= s[0] <= '9'

def ceil_(a, b):
	return (a + b - 1) // b
MOD = 10 ** 9 + 7

def solve():
	(N, M) = getInts()
	A = getInts()
	cnt = [0] * N
	poss = []
	for (i, a) in enumerate(A):
		cnt[(i + 1 - a) % N] += 1
	for i in range(N):
		if cnt[i] >= N - 2 * M:
			G = [[] for _ in range(N)]
			for (j, a) in enumerate(A):
				G[a - 1].append((j - i) % N)
				G[(j - i) % N].append(a - 1)
			tmp = 0
			used = [0] * N
			for j in range(N):
				if not G[j] or used[j]:
					continue
				Q = dq([j])
				used[j] = 1
				num = 1
				while Q:
					u = Q.popleft()
					for v in G[u]:
						if used[v]:
							continue
						used[v] = 1
						num += 1
						Q.append(v)
				tmp += num - 1
			if tmp <= M:
				poss.append(i)
	print(len(poss), *poss)
	return
for _ in range(getInt()):
	solve()


import sys
input = sys.stdin.readline
from collections import Counter
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	A = [a - 1 for a in A]
	B = [(i - a) % n for (i, a) in enumerate(A)]
	cnt = Counter(B)
	ans = []
	X = list(range(1, n + 1))
	for k in range(n):
		if n - cnt[k] > 2 * m:
			continue
		seen = [0] * n
		cycle = 0
		cur = A[k:] + A[:k]
		for i in range(n):
			if seen[i]:
				continue
			while not seen[i]:
				seen[i] = 1
				i = cur[i]
			cycle += 1
		if n - cycle <= m:
			ans.append(k)
	print(len(ans), *ans)


from collections import Counter

def solve():
	(n, m) = map(int, input().split())
	pp = [int(a) for a in input().split()]
	sc = Counter(((i - p) % n for (i, p) in enumerate(pp, 1)))
	candidates = [s for (s, c) in sc.most_common(3) if c >= n // 3]
	res = []
	for s in candidates:
		qq = [0] + pp[s:] + pp[:s]
		sc = 0
		visited = [False] * (n + 1)
		for i in range(1, n + 1):
			if visited[i]:
				continue
			j = i
			visited[i] = True
			while qq[j] != i:
				sc += 1
				j = qq[j]
				visited[j] = True
		if sc <= m:
			res.append(s)
	res.sort()
	print(len(res), *res)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	s = [0] * n
	for i in range(n):
		v = p[i] - 1
		s[(i - v) % n] += 1
	z = n - 2 * m
	r = []
	for i in range(n):
		if s[i] >= z:
			w = [True] * n
			c = 0
			for j in range(n):
				if w[j]:
					c += 1
					while w[j]:
						w[j] = False
						v = p[j] - 1
						j = (v + i) % n
			if n - c <= m:
				r.append(i)
	print(len(r), end=' ')
	print(' '.join(map(str, r)))
for i in range(int(input())):
	solve()


t = int(input())
results = []
for i in range(t):
	(n, m) = map(int, input().split())
	nums = [int(num) - 1 for num in input().split()]
	counts = {}
	for (j, num) in enumerate(nums):
		val = (j - num) % n
		counts[val] = counts.get(val, 0) + 1
	res = []
	for k in counts:
		if counts[k] < n - 2 * m:
			continue
		shifted = nums[k:] + nums[:k]
		tested = [True] * n
		to_swap = 0
		for index in range(len(tested)):
			current_count = 0
			current_index = index
			while True:
				if tested[current_index]:
					tested[current_index] = False
					current_count += 1
					current_index = shifted[current_index]
				else:
					break
			if current_count != 0:
				to_swap += current_count - 1
		if to_swap <= m:
			res.append(k)
	results.append(res)
for i in range(t):
	if len(results[i]) == 0:
		print(0)
	else:
		print(len(results[i]), end=' ')
		print(' '.join((str(k) for k in sorted(results[i]))))


import sys, math, os
from math import factorial, inf, gcd, pi, sqrt, ceil
from heapq import *
from functools import *
from itertools import *
from collections import *
sys.setrecursionlimit(10 ** 5)
if os.environ.get('HOME') == '/Users/clarity':
	os.chdir(os.path.dirname(os.path.abspath(__file__)))
	inp = open('E_test.txt', 'r').readline

	def debug(*args):
		print(*args, file=sys.stderr)
else:
	inp = sys.stdin.readline

	def debug(*args):
		pass

def line():
	return list(map(int, inp().rstrip().split()))

def fline():
	return list(map(float, inp().rstrip().split()))

def number():
	return int(inp())

def print_array(l):
	print(' '.join(list(map(str, l))))

def testcase(t):
	for p in range(t):
		solve()

def check_if_shift_is_achievable_in_m_pers(s, shift, m):
	m_left = m
	s = [(x - shift - 1) % len(s) for x in s]
	debug(s)
	to_update = {}
	for i in range(len(s)):
		while s[i] in to_update:
			s[i] = to_update[s[i]]
		if s[i] != i:
			to_update[i] = s[i]
			s[i] = i
			m_left -= 1
			if m_left < 0:
				return 0
	return 1

def solve():
	(n, m) = line()
	s = line()
	dist = [(s[i] - i - 1 + n) % n for i in range(n)]
	c = Counter(dist)
	potential_shifts = [x[0] for x in c.most_common(3)]
	debug(s, dist, potential_shifts)
	ans = []
	for shift in potential_shifts:
		if check_if_shift_is_achievable_in_m_pers(s, shift, m):
			ans.append((n - shift) % n)
	print(len(ans), ' '.join(list(map(str, sorted(ans)))))

def main():
	testcase(number())
main()


def check(A, n, m, k):
	shifted = [0] * n
	for i in range(n):
		shifted[(i + k) % n] = i
	goTo = [0] * n
	for i in range(n):
		goTo[shifted[i]] = A[i] - 1
	done = [False] * n
	total_swaps = 0
	for i in range(n - 1):
		if done[i]:
			continue
		done[i] = True
		cur = i
		while not done[goTo[cur]]:
			cur = goTo[cur]
			done[cur] = True
			total_swaps += 1
	return total_swaps <= m

def solve(A, n, m):
	cnt = [0] * n
	for (i, it) in enumerate(A):
		cnt[(i - it + 1) % n] += 1
	ans = []
	for k in range(n):
		if cnt[k] + 2 * m >= n and check(A, n, m, k):
			ans.append(k)
	print(len(ans), *ans)
for case in range(int(input())):
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	solve(A, n, m)


import sys
from sys import stdin

def uf_find(n, p):
	ufl = []
	while p[n] != n:
		ufl.append(n)
		n = p[n]
	for i in ufl:
		p[i] = n
	return n

def uf_union(a, b, p, rank):
	ap = uf_find(a, p)
	bp = uf_find(b, p)
	if ap == bp:
		return True
	else:
		if rank[ap] > rank[bp]:
			p[bp] = ap
		elif rank[ap] < rank[bp]:
			p[ap] = bp
		else:
			p[bp] = ap
			rank[ap] += 1
		return False
tt = int(stdin.readline())
for loop in range(tt):
	(n, m) = map(int, stdin.readline().split())
	p = list(map(int, stdin.readline().split()))
	for i in range(n):
		p[i] -= 1
	kdic = {}
	for i in range(n):
		if p[i] > i:
			ch = n - (p[i] - i)
		else:
			ch = i - p[i]
		if ch not in kdic:
			kdic[ch] = 0
		kdic[ch] += 1
	ans = []
	mindk = n - 2 * m
	for k in kdic:
		if kdic[k] >= mindk:
			plis = [i for i in range(n)]
			rank = [0] * n
			for i in range(n):
				uf_union((i - k) % n, p[i], plis, rank)
			swap = n
			for i in range(n):
				if uf_find(i, plis) == i:
					swap -= 1
			if swap <= m:
				ans.append(k)
	ans.sort()
	print(len(ans), *ans)


from collections import defaultdict

def count(k, A):
	M = {A[i]: i + 1 for i in range(len(A))}
	shifted = {i + 1: (i + k) % len(A) + 1 for i in range(len(A))}
	r = 0
	for a in range(1, len(A) + 1):
		while M[a] != shifted[a]:
			sa = shifted[a]
			v = (len(A) + M[a] - 1 - k) % len(A) + 1
			shifted[a] = M[a]
			shifted[v] = sa
			a = v
			r += 1
	return r
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split(' '))
	A = [int(e) for e in input().split(' ')]
	M = {A[i]: i + 1 for i in range(len(A))}
	K = defaultdict(int)
	for a in range(1, n + 1):
		if M[a] >= a:
			K[M[a] - a] += 1
		else:
			K[(M[a] + n - a) % n] += 1
	R = []
	for (k, v) in sorted(K.items()):
		if n - v <= 2 * m and count(k, A) <= m:
			R.append(k)
	print(' '.join((str(e) for e in [len(R)] + R)))


import collections
import math
import itertools
import sys

def fast_input():
	return sys.stdin.readline().strip()
input = fast_input

def ints_input():
	return list((int(x) for x in input().split()))

def solve():
	(n, m) = ints_input()
	array = ints_input()
	shifts = collections.Counter()
	for (i, c) in enumerate(array):
		shifts[(i + 1 + n - int(c)) % n] += 1
	possible = []
	for (shift, number) in shifts.items():
		if number + 2 * m < n:
			continue
		unshifted = array[shift:] + array[:shift]
		done = [False for _ in range(len(unshifted) + 1)]
		cycles = []
		for i in range(1, len(unshifted) + 1):
			if done[i]:
				continue
			else:
				looped = False
				cycle = 0
				x = i
				done[x] = True
				while not looped:
					x = unshifted[x - 1]
					cycle += 1
					done[x] = True
					if x == i:
						looped = True
				cycles.append(cycle)
		permutations = sum([c - 1 for c in cycles])
		if permutations <= m:
			possible.append(shift)
	possible.sort()
	print(' '.join([str(len(possible))] + [str(x) for x in possible]))
for _ in range(int(input())):
	solve()


def solve(k):
	q = p[k:] + p[:k]
	visited = [False] * n
	cnt = 0
	for i in range(n):
		t = i
		if not visited[t]:
			cnt += 1
			while not visited[t]:
				visited[t] = True
				t = q[t]
	return n - cnt <= m
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	p = [int(x) - 1 for x in input().split()]
	good_k = {}
	ans = []
	for i in range(n):
		k = (i - p[i] + n) % n
		good_k[k] = good_k[k] + 1 if k in good_k else 1
	for k in good_k:
		if good_k[k] >= n - 2 * m:
			if solve(k):
				ans.append(k)
	ans.sort()
	print(len(ans), *ans)


def solve(n, m, arr):
	intervals = [0] * n
	for i in range(n):
		v = arr[i] - 1
		intervals[(i - v) % n] += 1
	minimal = n - 2 * m
	output = []
	for k in range(n):
		if intervals[k] >= minimal:
			visited = [False] * n
			result = 0
			for x in range(n):
				curr = (x + k) % n
				if not visited[curr]:
					result += 1
					while not visited[curr]:
						visited[curr] = True
						curr = (arr[curr] + k - 1) % n
			if result >= n - m:
				output.append(k)
	print(len(output), end=' ')
	print(*output, sep=' ')
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	solve(n, m, arr)


import sys
input = sys.stdin.readline

class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)
		self.size = [1] * (n + 1)

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
			self.size[y] += self.size[x]
		else:
			self.par[y] = x
			self.size[x] += self.size[y]
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def same_check(self, x, y):
		return self.find(x) == self.find(y)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	l = [0] * n
	for i in range(n):
		l[(i + 1 - p[i]) % n] += 1
	res = []
	for i in range(n):
		if l[i] * 3 >= n:
			uf = UnionFind(n)
			for j in range(n):
				uf.unite((p[j] + i - 1) % n, j)
			d = [0] * n
			ans = n
			for j in range(n):
				j = uf.find(j)
				if d[j]:
					continue
				d[j] = 1
				ans -= 1
			if ans <= m:
				res.append(i)
	print(len(res), *res)


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]
INF = 10 ** 10

def solve(N, M, P):
	T = []
	K = dict()
	for i in range(N):
		v = (i - P[i]) % N
		T.append(v)
		K[v] = (i - P[i]) % N
	counter = collections.Counter(T)
	result = []
	for (v, n) in counter.items():
		if n >= N - 2 * M:
			k = K[v]
			swap_count = 0
			P1 = list(P)
			D1 = {v: i for (i, v) in enumerate(P1)}
			for i in range(N):
				a = (i - k) % N
				if P1[i] != a:
					swap_count += 1
					j = D1[a]
					(D1[P1[j]], D1[P1[i]]) = (D1[P1[i]], D1[P1[j]])
					(P1[i], P1[j]) = (P1[j], P1[i])
			if swap_count <= M:
				result.append(k)
	result.sort()
	return [len(result)] + result
T0 = int(input())
for _ in range(T0):
	(N, M) = map(int, input().split())
	P = list(map(lambda x: int(x) - 1, input().split()))
	print(*solve(N, M, P))


def comps(q, n):
	for i in range(n):
		q[i] -= 1
	vis = [0] * n
	ans = 0
	for i in range(n):
		if vis[i] == 1:
			continue
		j = i
		while vis[j] == 0:
			vis[j] = 1
			j = q[j]
		ans += 1
	return ans

def check(n, m, k, p):
	q = []
	for i in range(k, n):
		q.append(p[i])
	for i in range(k):
		q.append(p[i])
	if n - comps(q, n) <= m:
		return 1
	else:
		return 0
t = int(input())
for tt in range(t):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	cnt = [0] * n
	for i in range(n):
		pos = i + 1 - p[i]
		if pos < 0:
			pos += n
		cnt[pos] += 1
	cycles = []
	for i in range(n):
		if cnt[i] >= n - 2 * m and check(n, m, i, p):
			cycles.append(i)
	print(len(cycles), end=' ')
	for i in range(len(cycles)):
		print(cycles[i], end=' ')
	print()


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	ops = [n] * n
	ans = []
	for i in range(n):
		ops[(a[i] - (i + 1)) % n] -= 1
	for i in range(n):
		if ops[-i] <= 2 * m:
			count = n
			visited = [0] * n
			for j in range(n):
				curr = j
				if visited[j]:
					continue
				while visited[curr] == 0:
					visited[curr] = 1
					curr = (a[curr] + i - 1) % n
				count -= 1
			if count <= m:
				ans.append(i)
	print(len(ans))
	if ans:
		print(' '.join(map(str, ans)))


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	p = [int(x) for x in input().split()]
	correct = [0] * (n + 2)
	for i in range(n):
		if p[i] > i + 1:
			correct[n - (p[i] - (i + 1))] += 1
		else:
			correct[i + 1 - p[i]] += 1
	correct_needed = n - 2 * m
	candidates = []
	for i in range(n):
		if correct[i] >= correct_needed:
			candidates.append(i)
	ans = []
	for k in candidates:
		switches_needed = 0
		visited = [False] * (n + 2)
		for i in range(n):
			if visited[i]:
				continue
			component_size = 0
			node = i
			while visited[node] == False:
				visited[node] = True
				component_size += 1
				node = (p[node] + k - 1) % n
			switches_needed += component_size - 1
		if switches_needed <= m:
			ans.append(k)
	print(str(len(ans)) + ' ', end='')
	print(*ans)