Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a permutation $p_{1}, p_{2}, \ldots, p_{N}$ of the integers $1$ through $N$. You may perform up to $K$ operations of the following type:
Choose three pairwise distinct valid indices $i_{1}, i_{2}, i_{3}$. Note that these indices do not have to be chosen in increasing order.
Let's denote the values of $p_{i_{1}}$, $p_{i_{2}}$ and $p_{i_{3}}$ before this operation by $v_{1}$, $v_{2}$ and $v_{3}$ respectively.
Change $p_{i_{2}}$ to $v_{1}$, $p_{i_{3}}$ to $v_{2}$ and $p_{i_{1}}$ to $v_{3}$. In other words, perform a cyclic right shift on the elements $p_{i_{1}}, p_{i_{2}}, p_{i_{3}}$ in this order.

For example, the permutation $(1,4,3,2,5)$ can be changed to the permutation $(1,5,3,4,2)$ in one operation by choosing $i_{1} = 2$, $i_{2} = 4$ and $i_{3} = 5$.

Your task is to sort the permutation in increasing order. Note that you do not have to minimise the number of performed operations.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $K$.
The second line contains $N$ space-separated integers $p_{1}, p_{2}, \ldots, p_{N}$.

------  Output ------
For each test case:
If it is impossible to sort the given permutation using at most $K$ operations, print a single line containing the integer $-1$.
Otherwise, first, print a line containing a single integer $M$ ($0 ≤ M ≤ K$) ― the number of operations you want to perform.
Then, print $M$ lines describing these operations. For each $i$ ($1 ≤ i ≤ M$), the $i$-th of these lines should contain three space-separated integers $a_{i}$, $b_{i}$ and $c_{i}$ (pairwise distinct; $1 ≤ a_{i}, b_{i}, c_{i} ≤ N$) ― the indices on which the $i$-th operation is performed.

------  Constraints ------
$1 ≤ T ≤ 100$
$3 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ p_{i} ≤ N$ for each valid $i$
$p_{1}, p_{2}, \ldots, p_{N}$ are pairwise distinct
the sum of all $N$ over all test cases does not exceed $2 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (5 points):
$p_{i} = N-i+1$ for each valid $i$
$N ≤ 400$
$K = N^{2}$

Subtask #2 (45 points): $K = \lfloor \frac{2N}{3} \rfloor$

Subtask #3 (50 points): $K = \lfloor \frac{N}{2} \rfloor$

----- Sample Input 1 ------ 
1

4 2

3 2 4 1
----- Sample Output 1 ------ 
1

1 3 4
----- explanation 1 ------ 
Example case 1: We can sort the permutation by performing one cyclic right shift operation on the indices $1$, $3$ and $4$.

Difficulty: HARD
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
for tc in range(int(input())):
	(n, k) = [int(a) for a in input().split()]
	a = [0] + [int(a) for a in input().split()]
	res = []
	for i1 in range(1, n):
		while a[i1] != i1 and a[a[i1]] != i1:
			i2 = a[i1]
			i3 = a[i2]
			res += [[i1, i2, i3]]
			(a[i2], a[i3], a[i1]) = (i2, i3, a[i3])
	pair = [(i1, a[i1]) for i1 in range(1, n + 1) if a[i1] > i1]
	if len(pair) % 2:
		print(-1)
	else:
		while pair:
			(i1, i2) = pair.pop()
			(i3, i4) = pair.pop()
			res += [[i1, i2, i3], [i1, i4, i3]]
		print(len(res), *['\n' + ' '.join(map(str, r)) for r in res])


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	pp = [0] + list(map(int, input().split()))
	res = []
	for i1 in range(1, n):
		while pp[i1] != i1 and pp[pp[i1]] != i1:
			i2 = pp[i1]
			i3 = pp[i2]
			res.append([i1, i2, i3])
			(pp[i2], pp[i3], pp[i1]) = (i2, i3, pp[i3])
	pair = [(i1, pp[i1]) for i1 in range(1, n + 1) if pp[i1] > i1]
	if len(pair) % 2:
		print(-1)
		continue
	while pair:
		(i1, i2) = pair.pop()
		(i3, i4) = pair.pop()
		res = res + [[i1, i2, i3], [i1, i4, i3]]
	print(len(res))
	print(*[' '.join(map(str, r)) + '\n' for r in res], sep='\n')


def main():

	def solve():
		(n, k) = map(int, input().split())
		pp = [0] + [int(a) for a in input().split()]
		i1 = 1
		res = []
		cycle = set()
		i1 = 1
		while i1 < n:
			if pp[i1] != i1 and pp[pp[i1]] != i1:
				i2 = pp[i1]
				i3 = pp[i2]
				res.append([i1, i2, i3])
				(pp[i2], pp[i3], pp[i1]) = (i2, i3, pp[i3])
			else:
				i1 += 1
		pair = {(i1, pp[i1]) for i1 in range(1, n + 1) if pp[i1] > i1}
		if len(pair) % 2 == 1:
			print(-1)
			return
		while pair:
			(i1, i2) = pair.pop()
			(i3, i4) = pair.pop()
			res.append([i1, i2, i3])
			res.append([i1, i4, i3])
		print(len(res))
		for r in res:
			print(' '.join(map(str, r)))
	q = int(input())
	for _ in range(q):
		solve()
main()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	d1 = {}
	d2 = {}
	i = 1
	c = 0
	for j in l:
		d1[i] = j
		d2[j] = i
		i += 1
	l1 = []
	for i in range(1, n + 1):
		if i == d1[d1[i]] or i == d1[i]:
			continue
		else:
			k = [d1[i], d2[i], i]
			l1.append(k)
			(p, q, r) = k
			(d2[p], d2[d1[p]], d2[r]) = k
			(d1[p], d1[q], d1[r]) = (d1[r], d1[p], d1[q])
	l2 = []
	for i in d1:
		if i != d1[i] and i == d1[d1[i]]:
			y = [i, d1[i]]
			l2.extend(y)
			d1[i] = 0
	if len(l2) % 4 == 0:
		for i in range(0, len(l2), 4):
			(p, q, r, s) = l2[i:i + 4]
			l1.extend([[r, q, p], [s, r, q]])
	else:
		c = 1
	if c == 1 or m < len(l1):
		print(-1)
	else:
		print(len(l1))
		for (p, g, m) in l1:
			print(p, g, m)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = [i - 1 for i in arr]
	swap = [False] * n
	ans = []
	extra = []
	flag = 0
	for i in range(n):
		if swap[i] or i == arr[i]:
			continue
		else:
			index = [i + 1]
			swap[i] = True
			ind = arr[i]
			while ind != i:
				swap[ind] = True
				index.append(ind + 1)
				ind = arr[ind]
		x = len(index)
		if x == 2:
			extra.append(index)
			continue
		if x % 2 == 0:
			extra.append([index[0], index[-1]])
		for j in range(1, x - 1, 2):
			ans.append((index[0], index[j], index[j + 1]))
		if len(extra) + len(ans) > k:
			flag = 1
			break
	if flag == 1 or len(extra) % 2 != 0:
		print(-1)
	else:
		print(len(ans) + len(extra))
		for ans in ans:
			print(*ans)
		for i in range(0, len(extra), 2):
			print(extra[i][0], extra[i][1], extra[i + 1][0])
			print(extra[i][0], extra[i + 1][1], extra[i + 1][0])


def cycles(a, cycle_list):
	n = len(a)
	for i in range(1, n):
		dis_cycle = []
		while a[i] != i:
			dis_cycle.append([i, a[i]])
			t = a[i]
			a[i] = a[a[i]]
			a[t] = t
		if len(dis_cycle) > 0:
			cycle_list.append(dis_cycle)

def parity_sort(a):
	odd = 0
	box = [0] * len(a)
	i = -1
	j = len(a)
	for iter in a:
		if len(iter) % 2 == 0:
			i += 1
			box[i] = iter
		else:
			j -= 1
			box[j] = iter
			odd += 1
	if odd % 2 == 1:
		return -1
	extra = []
	for iter in range(j, len(a), 2):
		x1 = box[iter].pop(-1)
		x2 = box[iter + 1].pop(0)
		extra.append(box[iter])
		extra.append([x1, x2])
		extra.append(box[iter + 1])
	box = box[:i + 1] + extra
	return box

def shift(x1, x2):
	if x1[0] in x2 or x1[1] in x2:
		if x1[0] == x2[0]:
			return [[x1[0], x1[1], x2[1]]]
		elif x1[0] == x2[1]:
			return [[x1[0], x1[1], x2[0]]]
		elif x1[1] == x2[0]:
			return [[x1[1], x1[0], x2[1]]]
		else:
			return [[x1[1], x1[0], x2[0]]]
	else:
		return [[x1[0], x1[1], x2[1]], [x2[0], x2[1], x1[0]]]
t = int(input())
while t > 0:
	a = input().split()
	n = int(a[0])
	k = int(a[1])
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	a = [0] + a
	cycle_list = []
	cycles(a, cycle_list)
	cycle_list = parity_sort(cycle_list)
	if cycle_list == -1:
		print(-1)
	else:
		operations = []
		for i in cycle_list:
			if len(i) > 0:
				for j in range(0, len(i), 2):
					operations.extend(shift(i[j], i[j + 1]))
		if len(operations) > k:
			print(-1)
		else:
			print(len(operations))
			for i in operations:
				print(i[0], i[1], i[2])
	t -= 1


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().strip().split(' '))
	a = [0]
	a[1:] = list(map(int, input().strip().split(' ')))
	pivot = [False] * (n + 1)
	op = []
	re = []
	flag = 0
	for i in range(1, n + 1):
		if pivot[i] or a[i] == i:
			continue
		else:
			seq = []
			seq.append(i)
			pivot[i] = True
			j = a[i]
			while j != i:
				pivot[j] = True
				seq.append(j)
				j = a[j]
		x = len(seq)
		if x == 2:
			re.append(seq)
			continue
		if x % 2 == 0:
			re.append([seq[0], seq[-1]])
		for i in range(1, x - 1, 2):
			op.append([seq[0], seq[i], seq[i + 1]])
		if len(op) + len(re) > k:
			flag = 1
			break
	if flag == 1 or len(re) % 2 != 0:
		print(-1)
	else:
		print(len(op) + len(re))
		for op in op:
			print(*op)
		for i in range(0, len(re), 2):
			print(re[i][0], re[i][1], re[i + 1][0])
			print(re[i][0], re[i + 1][1], re[i + 1][0])


test = int(input())
while test > 0:
	test -= 1
	(nn, kk) = map(int, input().split())
	array = [int(i) for i in input().split()]
	array = [0] + array
	li = [0] * (nn + 1)
	(cc, dd) = (list(), list())
	counter = 0
	k = 1
	for j in range(1, nn + 1):
		li[array[j]] = j
	while k < nn + 1:
		if k != li[k]:
			rest = li[k]
			ee = k
			if array[k] == rest:
				dd.append(rest)
				dd.append(k)
				array[rest] = rest
				array[k] = k
				li[k] = k
				li[rest] = rest
			else:
				counter += 1
				rest1 = array[k]
				cc.append(rest)
				cc.append(ee)
				cc.append(rest1)
				array[rest] = array[rest1]
				array[rest1] = array[ee]
				array[ee] = k
				li[array[rest]] = rest
				li[array[rest1]] = rest1
				li[k] = k
		k = k + 1
	flag = 1
	if len(dd) % 4 == 0:
		for j in range(len(dd) // 4):
			counter = counter + 2
			cc.append(dd[4 * j])
			cc.append(dd[4 * j + 1])
			cc.append(dd[4 * j + 2])
			cc.append(dd[4 * j])
			cc.append(dd[4 * j + 3])
			cc.append(dd[4 * j + 2])
	else:
		flag = 0
	if flag == 1 and counter <= kk:
		print(counter)
		for z in range(counter):
			print(cc[3 * z], cc[3 * z + 1], cc[3 * z + 2])
	else:
		print(-1)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

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

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
t = int(input())
while t:
	freq = {}
	(size, m) = get_ints()
	arr = get_array()
	for i in range(size):
		freq[arr[i]] = i
	res = []
	n = 0
	for j in range(size):
		if arr[j] == j + 1:
			continue
		else:
			occurance1 = j
			random_occurance = arr[j]
			occurance3 = freq[j + 1]
			occurance2 = random_occurance - 1
			if arr[occurance1] == occurance2 + 1 and arr[occurance2] == occurance3 + 1 and (arr[occurance3] == occurance1 + 1) and (occurance2 != occurance3) or ((arr[occurance1] == occurance2 + 1 and arr[occurance2] == occurance3 + 1 or (arr[occurance2] == occurance3 + 1 and arr[occurance3] == occurance1 + 1) or (arr[occurance3] == occurance1 + 1 and arr[occurance1] == occurance2 + 1)) and occurance2 != occurance3):
				temp = arr[occurance3]
				arr[occurance3] = arr[occurance2]
				arr[occurance2] = arr[occurance1]
				arr[occurance1] = temp
				random_occurance = arr[occurance1]
				y = arr[occurance2]
				z = arr[occurance3]
				freq[random_occurance] = occurance1
				freq[y] = occurance2
				freq[z] = occurance3
				res.append(occurance1 + 1)
				res.append(occurance2 + 1)
				res.append(occurance3 + 1)
				n += 1
			else:
				continue
	for j in range(size):
		if arr[j] == j + 1:
			continue
		else:
			occurance1 = j
			random_occurance = arr[j]
			occurance3 = freq[j + 1]
			occurance2 = random_occurance - 1
			if occurance2 == occurance3:
				for q in range(occurance1 + 1, size):
					if arr[q] != q + 1 and occurance2 != q:
						occurance2 = q
						break
			temp = arr[occurance3]
			arr[occurance3] = arr[occurance2]
			arr[occurance2] = arr[occurance1]
			arr[occurance1] = temp
			random_occurance = arr[occurance1]
			y = arr[occurance2]
			z = arr[occurance3]
			freq[random_occurance] = occurance1
			freq[y] = occurance2
			freq[z] = occurance3
			if occurance2 == occurance3:
				n = m + 1
				break
			res.append(occurance1 + 1)
			res.append(occurance2 + 1)
			res.append(occurance3 + 1)
			n += 1
	if n <= m:
		print(n)
		for i in range(len(res)):
			if (i + 1) % 3 == 0:
				print(res[i], end='\n')
			else:
				print(res[i], end=' ')
	else:
		print(-1)
	t -= 1


try:
	for _ in range(int(input())):
		(n, kk) = map(int, input().split())
		list1 = list(map(int, input().split()))
		v = [0] * (n + 1)
		list1 = [0] + list1
		k = []
		dd = []
		ff = []
		for i in range(1, n + 1):
			if v[i] == 0:
				k = []
				x = list1[i]
				v[x] = 1
				k.append(i)
				k.append(x)
				while x != i:
					x = list1[x]
					v[x] = 1
					k.append(x)
				lll = len(k)
				k = k[0:lll - 1]
				lll -= 1
				if lll == 2:
					dd.append(k)
				elif lll >= 3:
					if lll % 2 != 0:
						j = 0
						while j < lll - 2:
							ff.append([k[0], k[j + 1], k[j + 2]])
							j += 2
					else:
						j = 0
						while j < lll - 3:
							ff.append([k[0], k[j + 1], k[j + 2]])
							j += 2
						dd.append([k[0], k[-1]])
		f = 0
		if len(dd) % 2 == 0:
			i = 0
			while i < len(dd) - 1:
				x1 = dd[i]
				x2 = dd[i + 1]
				ff.append([x1[0], x1[1], x2[1]])
				ff.append([x1[0], x2[0], x2[1]])
				i += 2
		else:
			f = 1
			print(-1)
		if f == 0:
			if len(ff) <= kk:
				print(len(ff))
				for i in range(len(ff)):
					print(*ff[i])
			else:
				print(-1)
except:
	pass


def solve(a, n, k):
	vis = [True if i == a[i] - 1 else False for i in range(n)]
	ans = 0
	res = []
	two = []
	for ind in range(n):
		if vis[ind]:
			continue
		j = ind
		count = 0
		s = []
		while vis[j] == False:
			s.append(j)
			vis[j] = True
			j = a[j] - 1
			count += 1
		if count % 2 != 0:
			ans += count // 2
			for p in range(1, count // 2 + 1):
				res.append([s[0]] + s[p * 2 - 1:2 * p + 1])
		else:
			ans += count // 2 - 1
			for p in range(1, count // 2):
				res.append([s[0]] + s[p * 2 - 1:2 * p + 1])
			two += [s[0], s[-1]]
			if len(two) > 2:
				ans += 2
				res.append(two[:3])
				res.append([two[0], two[3], two[2]])
				two.clear()
		if ans > k:
			return [-1, []]
	if len(two) > 0:
		return [-1, []]
	return [ans, res]
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	(count, s) = solve(a, n, k)
	print(count)
	for i in s:
		t = [j + 1 for j in i]
		print(*t)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	swap = [0] * n
	for i in range(n):
		if arr[i] == i + 1:
			swap[i] = 0
		else:
			swap[i] = 1
	s = []
	(odd, even, flag) = (0, 0, 0)
	for i in range(n):
		if swap[i] == 1:
			cycle = [i + 1]
			j = i
			while swap[j] == 1:
				res = arr[j]
				cycle.append(res)
				swap[j] = 0
				j = arr[j] - 1
			s.append(cycle)
	trp = []
	extra = []
	count = 0
	for i in range(len(s)):
		if len(s[i]) % 2 != 0 and len(s[i]) != 3:
			for j in range(int((len(s[i]) - 2) / 2)):
				trp.append([s[i][0], s[i][j * 2 + 1], s[i][j * 2 + 2]])
				temp = j * 2 + 2
				count = count + 1
			extra.append([s[i][0], s[i][-2]])
			even = even + 1
		elif len(s[i]) % 2 == 0 and len(s[i]) != 3:
			for j in range(int((len(s[i]) - 1) / 2)):
				trp.append([s[i][0], s[i][j * 2 + 1], s[i][j * 2 + 2]])
				count = count + 1
		else:
			extra.append(s[i][:2])
			even = even + 1
	if even % 2 == 0:
		i = 0
		while i < len(extra):
			trp.append([extra[i][0], extra[i][1], extra[i + 1][0]])
			trp.append([extra[i][0], extra[i + 1][1], extra[i + 1][0]])
			i = i + 2
	else:
		flag = 1
	if flag == 1 or even + count > k:
		print(-1)
	else:
		print(even + count)
		for i in range(len(trp)):
			for j in range(len(trp[i])):
				print(trp[i][j], end=' ')
			print()


def swap(i, arr):
	temp = arr[i]
	arr[i] = arr[arr[i]]
	arr[temp] = temp
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	arr = [0] + list(map(int, input().split()))
	countTransposition = 0
	listoflistoftransposition = list()
	nooftranspositionincycle = list()
	count = 0
	for i in range(1, n + 1):
		listoftransposition = list()
		while i != arr[i]:
			countTransposition += 1
			count += 1
			listoftransposition.append([i, arr[i]])
			swap(i, arr)
		if listoftransposition != []:
			nooftranspositionincycle.append(count)
			count = 0
			listoflistoftransposition.append(listoftransposition)
	if countTransposition & 1 == 1:
		print(-1)
	else:
		ans = list()
		m = 0
		lenoftranspositions = len(listoflistoftransposition)
		for i in range(lenoftranspositions):
			j = 1
			while j < nooftranspositionincycle[i]:
				templist = listoflistoftransposition[i][j - 1]
				templist.append(listoflistoftransposition[i][j][1])
				ans.append(templist)
				m += 1
				j += 2
		temp1 = []
		for i in range(lenoftranspositions):
			if nooftranspositionincycle[i] & 1 == 1:
				temp1.append(listoflistoftransposition[i][-1])
		i = 1
		while i <= len(temp1):
			temp11 = temp1[i - 1]
			temp11.append(temp1[i][1])
			temp12 = temp1[i]
			temp12.append(temp1[i - 1][0])
			ans.append(temp11)
			ans.append(temp12)
			m += 2
			i += 2
		print(m)
		for i in range(m):
			print(ans[i][0], ans[i][1], ans[i][2])


from sys import *
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	arr = list(map(int, stdin.readline().split()))
	for i in range(n):
		arr[i] -= 1
	ans = []
	count = 0
	flag = 0
	extra = []
	swapping = [True for i in range(n)]
	for i in range(n):
		if i == arr[i]:
			swapping[i] = False
	for i in range(n):
		if swapping[i]:
			index = []
			idx = i
			while swapping[idx]:
				index.append(idx)
				swapping[idx] = False
				idx = arr[idx]
			while len(index) > 2:
				p = index.pop()
				q = index.pop()
				r = index[-1]
				if len(index) == 1:
					index.pop()
				ans.append([r + 1, q + 1, p + 1])
				count += 1
			if len(index) == 2:
				extra.append([index.pop(), index.pop()])
	if len(extra) % 2 == 1:
		print(-1)
		continue
	while len(extra) > 1:
		p = extra.pop()
		q = extra.pop()
		ans.append([p[0] + 1, p[1] + 1, q[1] + 1])
		ans.append([q[0] + 1, q[1] + 1, p[0] + 1])
		count += 2
		if count > k:
			flag = 1
			break
	if flag == 1:
		print('-1')
		continue
	else:
		print(count)
		for i in ans:
			print(*i)


import sys

def sol(c):
	print(len(c))
	for j in c:
		p = [x + 1 for x in j]
		print(*p)
t = int(input())
for i in range(t):
	(n, k) = map(int, sys.stdin.readline().strip().split())
	a = list(map(int, sys.stdin.readline().strip().split()))
	for j in range(n):
		a[j] -= 1
	d = list(sorted(a))
	if a == d:
		print('0')
		continue
	res = {}
	for j in range(n):
		res[a[j]] = j
	val = []
	c = []
	valb = [False for j in range(n)]
	for j in range(n):
		if a[j] != j and valb[j] == False:
			pair = [res[j], j, a[j]]
			if a[a[j]] == j:
				val.append([j, a[j]])
				valb[j] = True
				valb[a[j]] = True
			else:
				temp1 = a[pair[2]]
				temp2 = a[pair[0]]
				temp3 = a[pair[1]]
				a[pair[0]] = temp1
				res[temp1] = pair[0]
				a[pair[1]] = temp2
				res[temp2] = pair[1]
				a[pair[2]] = temp3
				res[temp3] = pair[2]
				c.append(pair)
	if len(val) > 0:
		if len(val) % 2 == 1:
			print('-1')
			continue
		else:
			for j in range(0, len(val), 2):
				c.append([val[j][0], val[j][1], val[j + 1][1]])
				c.append([val[j][0], val[j + 1][0], val[j + 1][1]])
	if len(c) <= k:
		sol(c)
	else:
		print('-1')


def findParity(listPer, lenPer):
	newList = listPer.copy()
	totalTrans = 0
	for i in range(1, lenPer):
		while newList[i] != i:
			totalTrans += 1
			j = newList[i]
			(newList[i], newList[j]) = (newList[j], newList[i])
	if totalTrans % 2 == 0:
		return True
	else:
		return False

def getCycle(listPer, lenPer):
	listOfCycles = []
	for i in range(1, lenPer):
		cntr = 0
		curCycle = []
		while listPer[i] != i:
			j = listPer[i]
			(listPer[i], listPer[j]) = (listPer[j], listPer[i])
			cntr += 1
			curCycle.append((i, j))
		if curCycle:
			listOfCycles.append((cntr % 2, cntr, curCycle))
	return listOfCycles

def printOut(listOfCycles, k):
	(numOfOps, cycleLen) = (0, 0)
	for element in listOfCycles:
		if element[0] == 0:
			numOfOps += element[1] // 2
		else:
			numOfOps += element[1] // 2 + 1
		cycleLen += 1
	if numOfOps <= k:
		print(numOfOps)
		f = 0
		for i in range(cycleLen):
			if listOfCycles[i][0] == 0:
				for j in range(0, listOfCycles[i][1], 2):
					f = i + 1
					print(listOfCycles[i][2][j][0], listOfCycles[i][2][j][1], listOfCycles[i][2][j + 1][1])
			else:
				break
		flag = False
		s = 0
		for k in range(f, cycleLen):
			if flag:
				cur = listOfCycles[k][2][0]
				print(prev[0], prev[1], cur[1])
				print(cur[0], cur[1], prev[0])
			for j in range(s, listOfCycles[k][1] - 1, 2):
				print(listOfCycles[k][2][j][0], listOfCycles[k][2][j][1], listOfCycles[k][2][j + 1][1])
			if s == 0:
				prev = listOfCycles[k][2][-1]
				flag = True
				s = 1
			else:
				s = 0
				flag = False
	else:
		print(-1)

def main():
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		listPer = list(map(int, input().split()))
		listPer.insert(0, 0)
		if findParity(listPer, n + 1):
			listOfCycles = getCycle(listPer, n + 1)
			listOfCycles.sort(key=lambda i: i[0])
			printOut(listOfCycles, k)
		else:
			print(-1)
main()


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	arr = list(map(lambda x: int(x) - 1, input().split()))
	(even, odd) = ([], [])
	for i in range(n):
		if i == arr[i]:
			continue
		cycle = []
		while i != arr[i]:
			p = arr[i]
			cycle.append(p)
			(arr[i], arr[p]) = (arr[p], arr[i])
		if len(cycle) % 2:
			odd.append((i, cycle))
		else:
			even.append((i, cycle))
	if len(odd) % 2:
		print('-1')
		continue
	ans = []
	extra = None
	for (x, cycle) in odd:
		i = 0
		while i < len(cycle):
			if i + 1 < len(cycle):
				ans.append((x, cycle[i], cycle[i + 1]))
				i += 2
			elif extra is not None:
				ans.append((extra[0], extra[1], x))
				ans.append((x, extra[0], cycle[i]))
				extra = None
				i += 1
			else:
				extra = (x, cycle[i])
				i += 1
	for (x, cycle) in even:
		i = 0
		while i < len(cycle):
			ans.append((x, cycle[i], cycle[i + 1]))
			i += 2
	if len(ans) > k:
		print('-1')
	else:
		print(len(ans))
		for (i, j, k) in ans:
			print('{} {} {}'.format(i + 1, j + 1, k + 1))


t = int(input())
for _ in range(t):
	(n, ops) = tuple(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.insert(0, 0)
	visited = [False] * (n + 1)
	res = []
	left = []
	lsize = 0
	for i in range(1, n + 1):
		if visited[i] or arr[i] == i:
			visited[i] = True
			continue
		cycle = []
		j = i
		size = 0
		while not visited[j]:
			visited[j] = True
			j = arr[j]
			cycle.append(j)
			size += 1
		k = 2
		done = 0
		while k < size:
			res.append((cycle[0], cycle[k - 1], cycle[k]))
			k += 2
			done += 2
		if size - done == 2:
			left.append(cycle[0])
			left.append(cycle[size - 1])
			lsize += 2
		if lsize == 4:
			res.append((left[0], left[1], left[2]))
			res.append((left[0], left[3], left[2]))
			left = []
			lsize = 0
	if lsize == 2 or len(res) > ops:
		print(-1)
	else:
		print(len(res))
		for i in res:
			print(i[0], i[1], i[2])


def compare(a):
	if len(a) & 1:
		return -len(a)
	return len(a)
for t in range(int(input())):
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	p = [0] + p
	liswaps = []
	totalswaps = 0
	for i in range(1, n + 1):
		swaps = []
		while p[i] != i:
			swaps.append((i, p[i]))
			i1 = i
			i2 = p[i]
			(p[i1], p[i2]) = (p[i2], p[i1])
		if swaps:
			liswaps.append(swaps)
			totalswaps += len(swaps)
	if totalswaps & 1:
		print(-1)
	else:
		ans = []
		liswaps.sort(key=compare)
		j = 0
		for i in range(len(liswaps)):
			li = liswaps[i]
			while j + 1 < len(li):
				ans.append((li[j][0], li[j][1], li[j + 1][1]))
				j += 2
			if j < len(li):
				ans.append((li[j][0], li[j][1], liswaps[i + 1][0][0]))
				ans.append((li[j][0], liswaps[i + 1][0][1], liswaps[i + 1][0][0]))
				j = 1
			else:
				j = 0
		if len(ans) > k:
			print(-1)
		else:
			print(len(ans))
			for item in ans:
				print(*item)


def compare(a):
	if len(a) & 1:
		return -len(a)
	return len(a)
for T in range(int(input())):
	(N, K) = map(int, input().split())
	P = [0]
	P.extend(list(map(int, input().split())))
	listOfSwaps = []
	totalSwaps = 0
	for i in range(1, N + 1):
		swaps = []
		while P[i] != i:
			swaps.append((i, P[i]))
			i1 = i
			i2 = P[i]
			(P[i1], P[i2]) = (P[i2], P[i1])
		if swaps:
			listOfSwaps.append(swaps)
			totalSwaps += len(swaps)
	if totalSwaps & 1:
		print(-1)
	else:
		ans = []
		listOfSwaps.sort(key=compare)
		j = 0
		for i in range(len(listOfSwaps)):
			listOfSwap = listOfSwaps[i]
			while j + 1 < len(listOfSwap):
				ans.append((listOfSwap[j][0], listOfSwap[j][1], listOfSwap[j + 1][1]))
				j += 2
			if j < len(listOfSwap):
				ans.append((listOfSwap[j][0], listOfSwap[j][1], listOfSwaps[i + 1][0][1]))
				ans.append((listOfSwaps[i + 1][0][0], listOfSwaps[i + 1][0][1], listOfSwap[j][0]))
				j = 1
			else:
				j = 0
		if len(ans) > K:
			print(-1)
		else:
			print(len(ans))
			for item in ans:
				print(*item)


for _ in range(int(input())):
	(n, k) = (int(x) for x in input().split())
	arr = [int(x) for x in input().split()]
	ans = []
	swap = []
	arr = [0] + arr
	souma = [0] * (n + 1)
	for i in range(1, n + 1):
		souma[arr[i]] = i
	num = 0
	j = 1
	while j < n + 1:
		if souma[j] != j:
			if souma[j] == arr[j]:
				a = souma[j]
				b = souma[a]
				swap.append(souma[j])
				swap.append(j)
				souma[j] = j
				souma[arr[j]] = arr[j]
				arr[j] = j
				arr[a] = a
			if souma[j] != arr[j]:
				a = souma[j]
				b = souma[a]
				c = arr[j]
				ans.append(souma[j])
				ans.append(souma[arr[j]])
				ans.append(arr[j])
				souma[j] = j
				souma[arr[j]] = arr[j]
				souma[arr[arr[j]]] = a
				d = arr[arr[j]]
				arr[j] = j
				arr[c] = c
				arr[a] = d
				num += 1
		j += 1
	if len(swap) % 4 == 0:
		for i in range(len(swap) // 4):
			ans.append(swap[4 * i])
			ans.append(swap[4 * i + 1])
			ans.append(swap[4 * i + 2])
			ans.append(swap[4 * i])
			ans.append(swap[4 * i + 3])
			ans.append(swap[4 * i + 2])
	if num + len(swap) // 2 <= k and len(swap) % 4 == 0:
		print(num + len(swap) // 2)
		for nakiri in range(len(ans) // 3):
			print(ans[3 * nakiri], ans[3 * nakiri + 1], ans[3 * nakiri + 2])
	else:
		print(-1)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = [0] + list(map(int, input().split()))
	ans = []
	swapping = [False] * (N + 1)
	count = 0
	extra = []
	for i in range(1, N + 1):
		if A[i] != i:
			swapping[i] = True
	for i in range(1, N + 1):
		if A[i] != i:
			indices = []
			ind = i
			(first, last) = (-1, -1)
			while swapping[ind] == True:
				indices.append(ind)
				swapping[ind] = False
				ind = A[ind]
			if len(indices) % 2 == 0 and len(indices) > 0:
				first = indices[0]
				last = indices.pop()
			for j in range(1, len(indices) - 1, 2):
				ans.append((indices[0], indices[j], indices[j + 1]))
				count += 1
			if first != -1 and last != -1:
				extra.append((first, last))
		if count > K:
			break
	while len(extra) > 1:
		ans.append((extra[0][0], extra[0][1], extra[1][0]))
		ans.append((extra[0][0], extra[1][1], extra[1][0]))
		count += 2
		del extra[0]
		del extra[0]
	if len(extra) != 0 or count > K:
		print(-1)
	else:
		print(count)
		for i in range(len(ans)):
			print(*ans[i])


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a = [i - 1 for i in a]
	v = {}
	r = []
	doubles = []
	c = 0
	f = 0
	for i in range(n):
		while a[i] != i and i not in v:
			if c >= k:
				f = 1
				break
			x = i
			y = a[i]
			z = a[a[i]]
			if x != z:
				c += 1
				r.append([x + 1, y + 1, z + 1])
				(a[x], a[y], a[z]) = (a[z], a[x], a[y])
			else:
				doubles.append([min(x, y), max(x, y)])
				(v[x], v[y]) = (1, 1)
		if f == 1:
			break
	while len(doubles) > 1:
		p = doubles.pop()
		q = doubles.pop()
		r.append([q[0] + 1, q[1] + 1, p[0] + 1])
		r.append([q[0] + 1, p[1] + 1, p[0] + 1])
		c += 2
	if c > k or f == 1 or doubles:
		print(-1)
	else:
		print(len(r))
		for i in r:
			print(*i)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = [0]
	l.extend(list(map(int, input().split())))
	l1 = [0] * (n + 1)
	for i in range(1, n + 1):
		l1[l[i]] = i
	l2 = [0] * (n + 1)
	for i in range(1, n + 1):
		if l[i] != i:
			l2[i] = 1
	i = 1
	ans = []
	f = 0
	while i < n:
		if l[i] == i:
			i += 1
			continue
		a1 = l1[i]
		a2 = l[l1[i]]
		a3 = 0
		if l1[a1] != a1 and l1[a1] != a2 and (l2[l1[a1]] == 1):
			a3 = l1[a1]
		else:
			i += 1
			continue
		if a1 == a2 or a2 == a3 or a3 == a1:
			i += 1
			continue
		b1 = l[a1]
		b2 = l[a2]
		b3 = l[a3]
		l[a2] = b1
		l[a3] = b2
		l[a1] = b3
		l1[b1] = a2
		l1[b2] = a3
		l1[b3] = a1
		if l[a1] == a1:
			l2[a1] = 0
		else:
			l2[a1] = 1
		if l[a2] == a2:
			l2[a2] = 0
		else:
			l2[a2] = 1
		if l[a3] == a3:
			l2[a3] = 0
		else:
			l2[a3] = 1
		if l[b1] == b1:
			l2[b1] = 0
		else:
			l2[b1] = 1
		if l[b2] == b2:
			l2[b2] = 0
		else:
			l2[b2] = 1
		if l[b3] == b3:
			l2[b3] = 0
		else:
			l2[b3] = 1
		i += 1
		ans.append((a1, a2, a3))
	f = 0
	i = 1
	while i < n:
		if l[i] == i:
			i += 1
			continue
		a1 = l1[i]
		a2 = l[l1[i]]
		a3 = 0
		l2[a1] = 0
		l2[a2] = 0
		if l1[a1] != a1 and l1[a1] != a2 and (l2[l1[a1]] == 1):
			a3 = l1[a1]
		elif l1[l[l[i]]] != a1 and l1[l[l[i]]] != a2 and (l2[l1[l[l[i]]]] == 1):
			a3 = l1[l[l[i]]]
			(a1, a2, a3) = (a3, a1, a2)
		else:
			j = i + 1
			while j < i + 1 + n:
				if a3 != 0:
					break
				if l2[j % (n + 1)] == 1:
					a3 = j % (n + 1)
				j += 1
		if a1 == a2 or a2 == a3 or a3 == a1:
			f = 1
			break
		b1 = l[a1]
		b2 = l[a2]
		b3 = l[a3]
		l[a2] = b1
		l[a3] = b2
		l[a1] = b3
		l1[b1] = a2
		l1[b2] = a3
		l1[b3] = a1
		if l[a1] == a1:
			l2[a1] = 0
		else:
			l2[a1] = 1
		if l[a2] == a2:
			l2[a2] = 0
		else:
			l2[a2] = 1
		if l[a3] == a3:
			l2[a3] = 0
		else:
			l2[a3] = 1
		if l[b1] == b1:
			l2[b1] = 0
		else:
			l2[b1] = 1
		if l[b2] == b2:
			l2[b2] = 0
		else:
			l2[b2] = 1
		if l[b3] == b3:
			l2[b3] = 0
		else:
			l2[b3] = 1
		i += 1
		ans.append((a1, a2, a3))
	if f == 1:
		print(-1)
		continue
	f1 = False
	for i in range(1, n + 1):
		if l[i] != i:
			f1 = True
			break
	if f1 == True:
		print(-1)
	elif len(ans) > k:
		print(-1)
	else:
		print(len(ans))
		for i in range(len(ans)):
			print(*ans[i])


test = int(input())
while test:
	test -= 1
	(n, k) = map(int, input().split())
	p = [None] + list(map(int, input().split()))
	visited = [False for i in range(n + 1)]
	steps = []
	doubles = []
	steps_taken = 0
	for i in range(1, n + 1):
		if not visited[i]:
			cycles = []
			j = i
			while not visited[j]:
				visited[j] = True
				cycles.append(j)
				j = p[j]
			while len(cycles) > 2:
				z = cycles.pop()
				y = cycles.pop()
				x = cycles[-1]
				steps.append((x, y, z))
				steps_taken += 1
				if len(cycles) == 1:
					cycles.pop()
			if len(cycles) == 2:
				doubles.append(cycles)
	while len(doubles) > 1:
		pair1 = doubles.pop()
		pair2 = doubles.pop()
		(a, b) = (pair1[0], pair1[1])
		(c, d) = (pair2[0], pair2[1])
		steps.append((a, b, d))
		steps.append((d, a, c))
		steps_taken += 2
	if len(doubles) > 0 or len(steps) > k:
		print(-1)
	else:
		print(len(steps))
		for s in steps:
			print(str(s[0]) + ' ' + str(s[1]) + ' ' + str(s[2]))


T = int(input())

def rotate(a, b, c, arr, unsorted):
	n = 1
	arrl = [a, b, c]
	return (n, arrl)
for t in range(T):
	ns = input()
	num = list(map(int, ns.split()))
	n = num[0]
	kk = num[1]
	arr_s = input()
	arr = list(map(int, arr_s.split()))
	n = len(arr)
	l = []
	f = False
	inversions = []
	count = 0
	for i in range(n):
		while arr[i] != i + 1:
			if arr[i] != i + 1:
				ai = i + 1
				bi = arr[i]
				if ai == arr[bi - 1]:
					inversions.append(ai)
					inversions.append(bi)
					tp = arr[ai - 1]
					arr[ai - 1] = arr[bi - 1]
					arr[bi - 1] = tp
				else:
					ci = arr[bi - 1]
					tmp = arr[ai - 1]
					arr[ai - 1] = arr[ci - 1]
					arr[ci - 1] = arr[bi - 1]
					arr[bi - 1] = tmp
					l.append([ai, bi, ci])
					count += 1
				if count > kk:
					break
	if len(inversions) % 4 == 0:
		for i in range(int(len(inversions) / 4)):
			ai = inversions[4 * i]
			bi = inversions[4 * i + 1]
			ci = inversions[4 * i + 2]
			di = inversions[4 * i + 3]
			l.append([ai, ci, bi])
			l.append([bi, di, ci])
	else:
		print(-1)
		continue
	for i in range(len(arr)):
		if arr[i] != i + 1:
			f = True
			break
	if len(l) > kk or f:
		print(-1)
		continue
	print(len(l))
	for i in l:
		print(i[0], i[1], i[2])


def triple_sort(p, N, K):
	ans = 0
	res = []
	if_two = []
	visited = [True if i == p[i] - 1 else False for i in range(N)]
	for index in range(N):
		if visited[index] == True:
			continue
		temp = index
		cnt = 0
		a = []
		while visited[temp] == False:
			a.append(temp)
			visited[temp] = True
			temp = p[temp] - 1
			cnt += 1
		if cnt % 2 != 0:
			ans += cnt // 2
			for i in range(1, cnt // 2 + 1):
				res.append([a[0]] + a[i * 2 - 1:i * 2 + 1])
		else:
			ans += cnt // 2 - 1
			for i in range(1, cnt // 2):
				res.append([a[0]] + a[i * 2 - 1:i * 2 + 1])
			if_two += [a[0], a[-1]]
			if len(if_two) > 2:
				ans += 2
				res.append(if_two[:3])
				res.append([if_two[0], if_two[3], if_two[2]])
				if_two.clear()
		if ans > K:
			return (-1, [])
	if len(if_two) > 0:
		return (-1, [])
	else:
		return (ans, res)
for tc in range(int(input())):
	(N, K) = map(int, input().split())
	p_list = list(map(int, input().split()))
	(moves, ind_list) = triple_sort(p_list, N, K)
	print(moves)
	for each in ind_list:
		output = [inc + 1 for inc in each]
		print(*output)


def triple_sort(n, k, prm_list):
	checked = [True if i == prm_list[i] - 1 else False for i in range(n)]
	ans = 0
	even_cycle = []
	result = []
	for (index, flag) in enumerate(checked):
		if flag:
			continue
		cycle_list = []
		count = 0
		value = index
		while not checked[value]:
			checked[value] = True
			cycle_list.append(value)
			value = prm_list[value] - 1
			count += 1
		(temp_result, temp_even_cycle, temp_count) = swap_indexes(cycle_list, count, even_cycle)
		result += temp_result
		even_cycle = temp_even_cycle
		ans += temp_count
		if ans > k:
			return [-1, []]
	if len(even_cycle) > 0:
		return [-1, []]
	return [ans, result]

def swap_indexes(cycle_list, list_len, even_cycle):
	result = []
	count = 0
	if list_len % 2 != 0:
		count += list_len // 2
		for i in range(1, list_len // 2 + 1):
			result.append([cycle_list[0]] + cycle_list[i * 2 - 1:i * 2 + 1])
	else:
		count += list_len // 2 - 1
		for i in range(1, list_len // 2):
			result.append([cycle_list[0]] + cycle_list[i * 2 - 1:i * 2 + 1])
		even_cycle += [cycle_list[0], cycle_list[-1]]
		if len(even_cycle) > 2:
			count += 2
			result.append(even_cycle[:3])
			result.append([even_cycle[0]] + [even_cycle[3]] + [even_cycle[2]])
			even_cycle = []
	return (result, even_cycle, count)
test_case = int(input())
for i in range(test_case):
	(n, k) = map(int, input().split())
	m = k
	prm_list = list(map(int, input().split()))
	(k, result) = triple_sort(n, k, prm_list)
	print(k)
	for r in result:
		re = [m + 1 for m in r]
		print(*re)


ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda : int(input())
ip = lambda : [int(w) for w in input().split()]
from bisect import insort, bisect_left as bs
for _ in range(inp()):
	(n, k) = ip()
	x = ip()
	xind = {x[i]: i for i in range(n)}
	y = [i + 1 for i in range(n)]
	if x == y:
		print(0)
		continue
	ind = [i for i in range(n) if x[i] != y[i]]
	vis = {i: 1 for i in ind}
	(ans, dup) = ([], [])
	while len(ind) >= 3 and k:
		h = ind[0]
		i = xind[h + 1]
		j = xind[i + 1]
		if h == x[i] - 1 and i == x[h] - 1:
			dup.extend([h, i])
			ind = ind[1:]
			ix = bs(ind, i)
			ind.pop(ix)
			vis[i] = 0
			vis[h] = 0
			continue
		t = [h, j, i]
		(x[h], x[j], x[i]) = (x[i], x[h], x[j])
		(xind[x[h]], xind[x[j]], xind[x[i]]) = (h, j, i)
		for kk in t:
			if vis.get(kk, 0):
				if x[kk] == y[kk]:
					ix = bs(ind, kk)
					ind.pop(ix)
					vis[kk] = 0
		ans.append([ii + 1 for ii in t])
		k -= 1
	dup.extend(ind)
	if len(dup) % 4 != 0:
		print(-1)
		continue
	for i in range(0, len(dup) - 3, 4):
		(a, b, c, d) = dup[i:i + 4]
		(x[a], x[b], x[d]) = (x[d], x[a], x[b])
		(x[a], x[c], x[d]) = (x[d], x[a], x[c])
		ans.append([a + 1, b + 1, d + 1])
		ans.append([a + 1, c + 1, d + 1])
	if x != y:
		print(-1)
		continue
	print(len(ans))
	[print(*i) for i in ans]


import numpy as np
for i in range(int(input())):
	(N, K) = map(int, input().split())
	P = list(map(int, input().split()))
	T = []
	for i in range(N):
		P[i] -= 1
		if P[i] == i:
			T.append(True)
		else:
			T.append(False)
	Q = np.argsort(P)
	count = 0
	ans = []
	i = 0
	val = []
	while i < N:
		if T[i]:
			i += 1
			continue
		i3 = Q[i]
		i1 = i
		i2 = P[i]
		if i2 == i3:
			val.append([i1, i3])
			T[i1] = True
			T[i3] = True
			temp = Q[i1]
			Q[i1] = Q[i3]
			Q[i3] = temp
		else:
			temp = Q[P[i1]]
			Q[P[i1]] = Q[P[i2]]
			Q[P[i2]] = Q[P[i3]]
			Q[P[i3]] = temp
			temp = P[i1]
			P[i1] = P[i3]
			P[i3] = P[i2]
			P[i2] = temp
			ans.append([i1, i2, i3])
			if P[i1] == i1:
				T[i1] = True
			if P[i2] == i2:
				T[i2] = True
			if P[i3] == i3:
				T[i3] = True
			count += 1
		i += 1
	if len(val) > 0:
		if len(val) % 2 == 1:
			print('-1')
			continue
		else:
			for j in range(0, len(val), 2):
				ans.append([val[j][0], val[j][1], val[j + 1][1]])
				ans.append([val[j][0], val[j + 1][0], val[j + 1][1]])
				count += 2
	if count <= K:
		print(count)
		for i in ans:
			print(f'{i[0] + 1} {i[1] + 1} {i[2] + 1}')
	else:
		print('-1')


for _ in range(int(input())):
	(nn, kk) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = [0] + arr
	li = [0] * (nn + 1)
	concomp = []
	dd = []
	c = 0
	k = 1
	for j in range(1, nn + 1):
		li[arr[j]] = j
	while k < nn + 1:
		if k != li[k]:
			ele = li[k]
			e = k
			if arr[k] == ele:
				dd.append(ele)
				dd.append(k)
				arr[ele] = ele
				arr[k] = k
				li[k] = k
				li[ele] = ele
			else:
				c += 1
				ele1 = arr[k]
				concomp.append(ele)
				concomp.append(e)
				concomp.append(ele1)
				arr[ele] = arr[ele1]
				arr[ele1] = arr[e]
				arr[e] = k
				li[arr[ele]] = ele
				li[arr[ele1]] = ele1
				li[k] = k
		k += 1
	flag = 1
	if len(dd) % 4 == 0:
		for j in range(len(dd) // 4):
			c += 2
			concomp.append(dd[4 * j])
			concomp.append(dd[4 * j + 1])
			concomp.append(dd[4 * j + 2])
			concomp.append(dd[4 * j])
			concomp.append(dd[4 * j + 3])
			concomp.append(dd[4 * j + 2])
	else:
		flag = 0
	if flag == 1 and c <= kk:
		print(c)
		for z in range(c):
			print(concomp[3 * z], concomp[3 * z + 1], concomp[3 * z + 2])
	else:
		print(-1)


try:

	def change(list, pos1, pos2):
		(list[pos1], list[pos2]) = (list[pos2], list[pos1])
		return list
	test = input()
	test = int(test)
	tser = 0
	for tser in range(test):
		(N, Q) = map(int, input().split(' '))
		l = list(map(int, input().split(' ')))
		unsor = 0
		l = [0] + l
		i = 1
		while i <= N:
			if l[i] != i:
				unsor += 1
			i += 1
		if unsor == 0:
			print(0)
			continue
		if all((l[i] >= l[i + 1] for i in range(len(l) - 1))):
			if N % 4 != 0 or N % 4 != 1:
				print('-1')
			else:
				Q = 1
				p = N
				la = 0
				print(N // 2)
				for i in range(0, N // 2):
					print(p, Q, p - 1)
					la += 1
					if la == 2:
						la = 0
						p = p - 2
					Q += 1
		else:
			ran = 0
			p_p = 0
			fin = []
			i = 0
			while i < N + 1:
				th = i
				se = l[i]
				if i == l[l[i]]:
					i += 1
					continue
				else:
					fir = l[l[i]]
					change(l, th, se)
					change(l, th, fir)
					if l[se] == se:
						unsor -= 1
					if l[fir] == fir:
						unsor -= 1
					if l[th] == th:
						unsor -= 1
					ran += 1
					fin.append(th)
					fin.append(se)
					fin.append(fir)
				if ran > Q:
					p_p = -1
					break
			i = 1
			while i:
				if unsor > 0 and unsor <= 2:
					p_p = -1
					break
				else:
					th = i
					se = l[i]
					if th != se:
						for j in range(i, N + 1):
							if j != l[j] and j != th and (j != se):
								fir = j
								change(l, th, se)
								change(l, th, fir)
								ran += 1
								if l[fir] == fir:
									unsor -= 1
								if l[th] == th:
									unsor -= 1
								if l[se] == se:
									unsor -= 1
								fin.append(th)
								fin.append(se)
								fin.append(fir)
								break
					if i == l[i]:
						if i != N:
							i += 1
						else:
							break
					if ran > Q:
						p_p = -1
						break
			if unsor == 0 and p_p != -1 and (ran <= Q):
				p_p = ran
			if p_p != -1:
				print(ran)
				for i in range(0, len(fin), 3):
					print(fin[i], fin[i + 1], fin[i + 2])
			else:
				print(-1)
				continue
except:
	pass


from collections import Counter

def check(arr, k):
	result = []
	count = 0
	arr2 = []
	c = set()
	d = {}
	j = 0
	for i in arr:
		d[i] = j
		j += 1
	brr = sorted(arr)
	for i in range(len(arr)):
		if arr[i] != i + 1:
			index3 = d[i + 1]
			index2 = d[index3 + 1]
			index1 = i
			if index1 != index2 and index2 != index3 and (index3 != index1):
				temp = arr[index1]
				arr[index1] = arr[index3]
				arr[index3] = arr[index2]
				arr[index2] = temp
				d[arr[index1]] = index1
				d[arr[index2]] = index2
				d[arr[index3]] = index3
				result.append([index1, index2, index3])
			else:
				count += 1
				if i not in c:
					arr2.extend([arr[i] - 1, i])
					c.add(arr[i] - 1)
					c.add(i)
	if count % 4 != 0:
		return -1
	else:
		for i in range(len(arr2) - 2):
			if arr[arr2[i]] != arr2[i] + 1:
				index2 = arr2[i + 2]
				index3 = arr2[i + 1]
				index1 = arr2[i]
				temp = arr[index1]
				arr[index1] = arr[index3]
				arr[index3] = arr[index2]
				arr[index2] = temp
				d[arr[index1]] = index1
				d[arr[index2]] = index2
				d[arr[index3]] = index3
				result.append([index1, index2, index3])
	if arr == brr:
		return result
	return -1
t = int(input())
while t:
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	result = check(arr, k)
	if result == -1:
		print(result)
	else:
		print(len(result))
		for (i1, i2, i3) in result:
			print(i1 + 1, i2 + 1, i3 + 1)
	t -= 1


def shifting(i, j, k, a):
	flg = a[i]
	a[i] = a[j]
	a[j] = a[k]
	a[k] = flg

def fuu(a, b, n, k, res):
	yes = 0
	for i in range(1, n + 1):
		if a[i] != i and i != b[b[i]]:
			x = i
			y = a[i]
			z = b[i]
			if y == z:
				if (b[b[i]] != b[i] and b[b[i]] != i) and a[b[i]] != b[i]:
					y = b[b[i]]
				else:
					y = i
					while True:
						y += 1
						if y >= n + 1:
							break
						if (a[y] != y and x != y) and y != z:
							break
				if y == n + 1:
					yes = 1
					break
			shifting(z, y, x, a)
			res.append([x, y, z])
			b[a[x]] = x
			b[a[z]] = z
			b[a[y]] = y
	yes = 0
	for i in range(1, n + 1):
		if a[i] != i:
			x = i
			y = a[i]
			z = b[i]
			if y == z:
				if (b[b[i]] != b[i] and b[b[i]] != i) and a[b[i]] != b[i]:
					y = b[b[i]]
				else:
					y = i
					while True:
						y += 1
						if y >= n + 1:
							break
						if (a[y] != y and x != y) and y != z:
							break
				if y == n + 1:
					yes = 1
					break
			shifting(z, y, x, a)
			res.append([x, y, z])
			b[a[x]] = x
			b[a[z]] = z
			b[a[y]] = y
	return (yes, res)
t = int(input())
while t:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.insert(0, 0)
	b = [0] * (n + 1)
	for i in range(1, n + 1):
		b[a[i]] = i
	res = []
	yes = 0
	(yes, res) = fuu(a, b, n, k, res)
	if len(res) > k:
		yes = 1
	if yes == 0:
		print(len(res))
		for h in range(len(res)):
			z = res[h]
			for i in range(len(z)):
				print(z[i], end=' ')
			print()
	else:
		print('-1')
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	psort = sorted(p)
	flag = 0
	for i in range(0, n):
		if p[i] != psort[i]:
			flag = 1
			break
	dflag = 0
	if psort == p[::-1]:
		dflag = 1
	if flag == 0:
		print(0)
	elif dflag == 1:
		if n == 3:
			print(-1)
		elif n % 4 == 0 or n % 4 == 1:
			print(n // 2)
			i = 1
			j = n
			for k in range(n // 4):
				print(i, i + 1, n)
				print(i + 1, n, n - 1)
				i = i + 2
				n = n - 2
		else:
			print(-1)
	elif flag == 1:
		unsor = 0
		p.insert(0, 0)
		for i in range(1, n + 1):
			if p[i] != i:
				unsor += 1
		final = []
		ans = 0
		i = 1
		counter = 0
		while i < n + 1:
			a = i
			b = p[i]
			if i == p[p[i]]:
				i += 1
				continue
			else:
				a = i
				b = p[i]
				c = p[p[i]]
				(p[a], p[b]) = (p[b], p[a])
				(p[a], p[c]) = (p[c], p[a])
				if p[a] == a:
					unsor -= 1
				if p[b] == b:
					unsor -= 1
				if p[c] == c:
					unsor -= 1
				counter += 1
				final.append([a, b, c])
			if counter > k:
				ans = -1
				break
		i = 1
		while i:
			if unsor > 0 and unsor <= 2:
				ans = -1
				break
			else:
				a = i
				b = p[i]
				if a != b:
					for j in range(i, n + 1):
						if j != a and j != b and (p[j] != j):
							c = j
							(p[a], p[b]) = (p[b], p[a])
							(p[a], p[c]) = (p[c], p[a])
							counter += 1
							if p[a] == a:
								unsor -= 1
							if p[b] == b:
								unsor -= 1
							if p[c] == c:
								unsor -= 1
							final.append([a, b, c])
							break
			if i == p[i]:
				if i == n:
					break
				else:
					i = i + 1
			if counter > k:
				ans = -1
				break
		if ans == -1:
			print(-1)
		else:
			print(len(final))
			for i in final:
				print(*i)


def solver(test):
	res = ''
	t_var = t_var2 = 0
	size = 0
	(n, k) = map(int, input().split())
	rangelist = list(map(int, input().split()))
	pos = [0 for i in range(n + 1)]
	dictionary = {}
	for i in range(1, n + 1):
		pos[i] = rangelist[i - 1]
		dictionary[pos[i]] = i
	for i in range(1, n + 1):
		if pos[i] != i:
			first = i
			second = pos[first]
			third = pos[second]
			if pos[pos[pos[first]]] == first and (not pos[pos[i]] == i):
				res += str(first) + ' ' + str(second) + ' ' + str(third) + '\n'
				size += 1
				pos[second] = second
				pos[third] = third
				pos[first] = first
				dictionary[second] = second
				dictionary[third] = third
				dictionary[i] = i
	for i in range(1, n + 1):
		if pos[i] != i:
			if pos[pos[i]] != i:
				res += str(i) + ' ' + str(pos[i]) + ' ' + str(dictionary[i]) + '\n'
				size += 1
				ip1 = i
				ip2 = pos[i]
				ip3 = dictionary[i]
				vi1 = pos[i]
				vi2 = pos[pos[i]]
				vi3 = pos[dictionary[i]]
				dictionary[vi1] = ip2
				dictionary[vi2] = ip3
				dictionary[vi3] = ip1
				pos[ip2] = vi1
				pos[ip1] = vi3
				pos[ip3] = vi2
	for i in range(1, n + 1):
		if pos[i] != i:
			if pos[pos[i]] == i:
				if t_var == 0 and t_var2 == 0:
					t_var = i
					t_var2 = pos[i]
				elif i != t_var2:
					res += str(t_var) + ' ' + str(i) + ' ' + str(t_var2) + '\n'
					size += 1
					ip1 = t_var
					ip2 = i
					ip3 = t_var2
					vi1 = pos[ip1]
					vi2 = pos[ip2]
					vi3 = pos[ip3]
					dictionary[vi1] = ip2
					dictionary[vi2] = ip3
					dictionary[vi3] = ip1
					pos[ip2] = vi1
					pos[ip1] = vi3
					pos[ip3] = vi2
					t_var = t_var2 = 0
			else:
				res += str(i) + ' ' + str(pos[i]) + ' ' + str(dictionary[i]) + '\n'
				size += 1
				ip1 = i
				ip2 = pos[i]
				ip3 = dictionary[i]
				vi1 = pos[ip1]
				vi2 = pos[ip2]
				vi3 = pos[ip3]
				dictionary[vi1] = ip2
				dictionary[vi2] = ip3
				dictionary[vi3] = ip1
				pos[ip2] = vi1
				pos[ip1] = vi3
				pos[ip3] = vi2
	c_var = 0
	for i in range(1, n + 1):
		if pos[i] != i:
			c_var = 1
			break
	if c_var:
		print(-1)
	elif size > k:
		print(-1)
	else:
		print(size)
		print(res, end='')
	return
t = int(input())
for tmp in range(t):
	solver(tmp)


def ans(length, arr, s):
	index = {}
	for i in range(1, length + 1):
		index[arr[i - 1]] = i
	isVisited = [False] * (length + 1)
	dic = {}
	for i in range(length):
		dic[i + 1] = arr[i]
	cycle = 1
	two_arr = []
	three_arr = []
	ans_val = 0
	z = 0
	for i in range(1000):
		z += 1
	ans_arr = []
	for k in range(1, length + 1):
		nextNode = 0
		index_arr = []
		if isVisited[k] == False:
			isVisited[k] = True
			if k == dic[k]:
				continue
			else:
				c = dic[k]
				index_arr.append(k)
				while not isVisited[c]:
					isVisited[c] = True
					nextNode = dic[c]
					c = nextNode
					cycle += 1
					index_arr.append(index[c])
				if cycle > 2:
					if cycle % 2 != 0:
						ans_val += cycle // 2
						c = 0
						temp = []
						for i in index_arr[::-1]:
							temp.append(i)
							c += 1
							if c == 3:
								temp.reverse()
								ans_arr.append(temp)
								temp = [i]
								c = 1
						cycle = 1
					else:
						temp = []
						c = 0
						if len(two_arr) != 0:
							ans_val += (cycle - 1) // 2
							for i in index_arr[-1:0:-1]:
								temp.append(i)
								c += 1
								if c == 3:
									temp.reverse()
									ans_arr.append(temp)
									temp = [i]
									c = 1
							temp = []
							temp = two_arr.pop()
							ans_val += 2
							ans_arr.append([temp[1], index_arr[0], index_arr[1]])
							ans_arr.append([temp[0], temp[1], index_arr[0]])
						elif len(three_arr) != 0:
							temp = []
							c = 0
							for i in index_arr[-1:0:-1]:
								temp.append(i)
								c += 1
								if c == 3:
									temp.reverse()
									ans_arr.append(temp)
									temp = [i]
									ans_val += 1
									c = 1
							a = three_arr.pop()
							temp = []
							c = 0
							for i in a[-1:0:-1]:
								temp.append(i)
								c += 1
								if c == 3:
									temp.reverse()
									ans_arr.append(temp)
									temp = [i]
									ans_val += 1
									c = 1
							ans_val += 2
							ans_arr.append([a[1], index_arr[0], index_arr[1]])
							ans_arr.append([a[0], a[1], index_arr[0]])
						else:
							three_arr.append(index_arr)
				elif cycle == 2:
					temp = []
					if len(two_arr) != 0:
						temp = two_arr.pop()
						ans_val += 2
						ans_arr.append([temp[1], index_arr[0], index_arr[1]])
						ans_arr.append([temp[0], temp[1], index_arr[0]])
					elif len(three_arr) != 0:
						a = three_arr.pop()
						temp = []
						c = 0
						for i in a[-1:0:-1]:
							temp.append(i)
							c += 1
							if c == 3:
								temp.reverse()
								ans_arr.append(temp)
								temp = [i]
								ans_val += 1
								c = 1
						ans_val += 2
						ans_arr.append([a[1], index_arr[0], index_arr[1]])
						ans_arr.append([a[0], a[1], index_arr[0]])
					else:
						two_arr.append(index_arr)
				cycle = 1
	if len(two_arr) != 0 or len(three_arr) != 0:
		print(-1)
	elif ans_val > k:
		print(-1)
	else:
		print(ans_val)
		for i in ans_arr:
			print(' '.join(map(str, i)))
t = int(input())
for i in range(t):
	a = input().split()
	n = int(a[0])
	s = int(a[1])
	arr = list(map(int, input().split()))
	ans(n, arr, s)


try:
	test = int(input())
	for _ in range(test):
		(n, m) = map(int, input().split())
		l = list(map(int, input().split()))
		d1 = {}
		d2 = {}
		i = 1
		cont = 0
		for j in l:
			d1[i] = j
			d2[j] = i
			i += 1
		l1 = []
		for i in range(1, n + 1):
			if i == d1[d1[i]] or i == d1[i]:
				continue
			else:
				k = [d1[i], d2[i], i]
				l1.append(k)
				(p, q, r) = k
				(d2[p], d2[d1[p]], d2[r]) = k
				(d1[p], d1[q], d1[r]) = (d1[r], d1[p], d1[q])
		l2 = []
		for i in d1:
			try:
				if i != d1[i] and i == d1[d1[i]]:
					y = [i, d1[i]]
					l2.extend(y)
					d1[i] = 0
			except:
				pass
		if len(l2) % 4 == 0:
			for i in range(0, len(l2), 4):
				u = l2[i:i + 4]
				(p, q, r, s) = u
				l1.extend([[r, q, p], [s, r, q]])
		else:
			cont = 1
		if cont == 1 or m < len(l1):
			print(-1)
		else:
			print(len(l1))
			for (p, g, m) in l1:
				print(p, g, m)
except EOFError:
	pass


ti = int(input())
while ti:
	ti -= 1
	(n, k) = map(int, input().strip().split(' '))
	a = [0]
	a[1:] = list(map(int, input().strip().split(' ')))
	pivot = [False] * (n + 1)
	abcd = []
	eenCin = []
	fag = 0
	for i in range(1, n + 1):
		if pivot[i] or a[i] == i:
			continue
		else:
			chain = []
			chain.append(i)
			pivot[i] = True
			j = a[i]
			while j != i:
				pivot[j] = True
				chain.append(j)
				j = a[j]
		x = len(chain)
		if x == 2:
			eenCin.append(chain)
			continue
		if x % 2 == 0:
			eenCin.append([chain[0], chain[-1]])
		for i in range(1, x - 1, 2):
			abcd.append([chain[0], chain[i], chain[i + 1]])
		if len(abcd) + len(eenCin) > k:
			fag = 1
			break
	if fag == 1 or len(eenCin) % 2 != 0:
		print(-1)
	else:
		print(len(abcd) + len(eenCin))
		for op in abcd:
			print(*op)
		for i in range(0, len(eenCin), 2):
			print(eenCin[i][0], eenCin[i][1], eenCin[i + 1][0])
			print(eenCin[i][0], eenCin[i + 1][1], eenCin[i + 1][0])


import sys

def printRes(res):
	print(len(result))
	for a in result:
		print(a)

def sortThreeno(P, n, k):
	for j in range(n):
		if len(done) == 0:
			v1 = False
			v2 = False
			v3 = False
			if not P[j] == j + 1:
				newid = dp[j + 1]
				v1 = [P[j], j + 1]
				v2 = [j + 1, newid + 1]
				temp = newid + 1
				v3 = [temp, dp[temp] + 1]
				if v1[0] == dp[temp] + 1:
					if v1 and v2 and v3:
						ind = []
						P[v1[1] - 1] = v2[0]
						P[v2[1] - 1] = v3[0]
						P[v3[1] - 1] = v1[0]
						dp[v2[0]] = v1[1] - 1
						dp[v3[0]] = v2[1] - 1
						dp[v1[0]] = v3[1] - 1
						ind.append(v1[1])
						ind.append(v3[1])
						ind.append(v2[1])
						result.append(' '.join(map(str, ind)))
						v1 = False
						v2 = False
						v3 = False
					else:
						print(-1)
						done.append(0)
						return

def sortTwono(P, n, k):
	for j in range(n):
		if len(done) == 0:
			v1 = False
			v2 = False
			v3 = False
			if not P[j] == j + 1:
				newid = dp[j + 1]
				newid2 = P[P[j] - 1]
				v1 = [P[j], j + 1]
				v2 = [j + 1, newid + 1]
				temp = newid + 1
				temp1 = newid2
				if v1[0] == dp[temp] + 1:
					v3 = [temp, dp[temp] + 1]
					if v1 and v2 and v3:
						ind = []
						P[v1[1] - 1] = v2[0]
						P[v2[1] - 1] = v3[0]
						P[v3[1] - 1] = v1[0]
						dp[v2[0]] = v1[1] - 1
						dp[v3[0]] = v2[1] - 1
						dp[v1[0]] = v3[1] - 1
						ind.append(v1[1])
						ind.append(v3[1])
						ind.append(v2[1])
						result.append(' '.join(map(str, ind)))
						v1 = False
						v2 = False
						v3 = False
					else:
						print(-1)
						done.append(0)
						return
				elif not v1[0] == temp1 and (not v2[0] == temp1):
					v3 = [temp1, dp[temp1] + 1]
					if v1 and v2 and v3:
						ind = []
						P[v1[1] - 1] = v2[0]
						P[v2[1] - 1] = v3[0]
						P[v3[1] - 1] = v1[0]
						dp[v2[0]] = v1[1] - 1
						dp[v3[0]] = v2[1] - 1
						dp[v1[0]] = v3[1] - 1
						ind.append(v1[1])
						ind.append(v3[1])
						ind.append(v2[1])
						result.append(' '.join(map(str, ind)))
						v1 = False
						v2 = False
						v3 = False
					else:
						print(-1)
						done.append(0)
						return
				elif not temp == v1[0]:
					v3 = [temp, dp[temp] + 1]
					if v1 and v2 and v3:
						ind = []
						P[v1[1] - 1] = v2[0]
						P[v2[1] - 1] = v3[0]
						P[v3[1] - 1] = v1[0]
						dp[v2[0]] = v1[1] - 1
						dp[v3[0]] = v2[1] - 1
						dp[v1[0]] = v3[1] - 1
						ind.append(v1[1])
						ind.append(v3[1])
						ind.append(v2[1])
						result.append(' '.join(map(str, ind)))
						v1 = False
						v2 = False
						v3 = False
					else:
						print(-1)
						done.append(0)
						return

def sortArrno(P, n, k):
	for j in range(n):
		if len(done) == 0:
			v1 = False
			v2 = False
			v3 = False
			if not P[j] == j + 1:
				newid = dp[j + 1]
				newid2 = P[P[j] - 1]
				v1 = [P[j], j + 1]
				v2 = [j + 1, newid + 1]
				temp = newid + 1
				temp1 = newid2
				if v1[0] == dp[temp] + 1:
					v3 = [temp, dp[temp] + 1]
					if v1 and v2 and v3:
						ind = []
						P[v1[1] - 1] = v2[0]
						P[v2[1] - 1] = v3[0]
						P[v3[1] - 1] = v1[0]
						dp[v2[0]] = v1[1] - 1
						dp[v3[0]] = v2[1] - 1
						dp[v1[0]] = v3[1] - 1
						ind.append(v1[1])
						ind.append(v3[1])
						ind.append(v2[1])
						result.append(' '.join(map(str, ind)))
						v1 = False
						v2 = False
						v3 = False
					else:
						print(-1)
						done.append(0)
						return
				elif not v1[0] == temp1 and (not v2[0] == temp1):
					v3 = [temp1, dp[temp1] + 1]
					if v1 and v2 and v3:
						ind = []
						P[v1[1] - 1] = v2[0]
						P[v2[1] - 1] = v3[0]
						P[v3[1] - 1] = v1[0]
						dp[v2[0]] = v1[1] - 1
						dp[v3[0]] = v2[1] - 1
						dp[v1[0]] = v3[1] - 1
						ind.append(v1[1])
						ind.append(v3[1])
						ind.append(v2[1])
						result.append(' '.join(map(str, ind)))
						v1 = False
						v2 = False
						v3 = False
					else:
						print(-1)
						done.append(0)
						return
				elif not temp == v1[0]:
					v3 = [temp, dp[temp] + 1]
					if v1 and v2 and v3:
						ind = []
						P[v1[1] - 1] = v2[0]
						P[v2[1] - 1] = v3[0]
						P[v3[1] - 1] = v1[0]
						dp[v2[0]] = v1[1] - 1
						dp[v3[0]] = v2[1] - 1
						dp[v1[0]] = v3[1] - 1
						ind.append(v1[1])
						ind.append(v3[1])
						ind.append(v2[1])
						result.append(' '.join(map(str, ind)))
						v1 = False
						v2 = False
						v3 = False
					else:
						print(-1)
						done.append(0)
						return
				else:
					for i in range(j + 1, n):
						if not P[i] == i + 1 and (not i == newid):
							v3 = [P[i], i + 1]
							break
					if v1 and v2 and v3:
						ind = []
						P[v1[1] - 1] = v2[0]
						P[v2[1] - 1] = v3[0]
						P[v3[1] - 1] = v1[0]
						dp[v2[0]] = v1[1] - 1
						dp[v3[0]] = v2[1] - 1
						dp[v1[0]] = v3[1] - 1
						ind.append(v1[1])
						ind.append(v3[1])
						ind.append(v2[1])
						result.append(' '.join(map(str, ind)))
						v1 = False
						v2 = False
						v3 = False
					else:
						print(-1)
						done.append(0)
						return 0
for _ in range(int(input())):
	(n, k) = map(int, sys.stdin.readline().split())
	P = list(map(int, sys.stdin.readline().split()))
	p1 = [i for i in range(1, n + 1)]
	dp = {}
	count = 0
	dp = {k1: v12 for (v12, k1) in enumerate(P)}
	result = []
	done = []
	possible = False
	sortThreeno(P, n, k)
	sortTwono(P, n, k)
	sortArrno(P, n, k)
	if P == p1:
		if len(result) <= k:
			printRes(result)
		else:
			print(-1)


def solve():
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	arr = [int(i) for i in input().split()]
	vp = [[i, ind] for (ind, i) in enumerate(arr)]
	ans = ''
	cnt = 0
	vp.sort()
	a = [-1] * n
	index = [-1] * n
	for i in range(n):
		a[vp[i][1]] = i
		index[i] = vp[i][1]
	s = []
	for i in range(n):
		if a[i] == i or (len(s) != 0 and i == s[-1][1]):
			continue
		tmp1 = a[i]
		tmp2 = index[i]
		if a[tmp1] != i:
			tmp3 = a[tmp1]
			index[i] = i
			index[tmp1] = tmp1
			tmp = a[tmp2]
			a[tmp2] = a[tmp1]
			a[tmp1] = a[i]
			a[i] = tmp
			index[tmp3] = tmp2
			ans += str(tmp2 + 1) + ' ' + str(i + 1) + ' ' + str(tmp1 + 1) + '\n'
			cnt += 1
			continue
		if len(s) != 0 and i == s[-1][1]:
			continue
		if len(s) == 0:
			s += [[i, a[i]]]
			continue
		p = s[-1]
		s.pop()
		tmp = a[i]
		a[i] = a[p[1]]
		a[p[1]] = a[p[0]]
		a[p[0]] = tmp
		tmp = a[i]
		a[i] = a[tmp1]
		a[tmp1] = a[p[0]]
		a[p[0]] = tmp
		ans += str(p[0] + 1) + ' ' + str(p[1] + 1) + ' ' + str(i + 1) + '\n'
		ans += str(p[0] + 1) + ' ' + str(tmp1 + 1) + ' ' + str(i + 1) + '\n'
		cnt += 2
		index[p[0]] = p[0]
		index[tmp1] = tmp1
		index[i] = i
		index[p[1]] = p[1]
		continue
	f = True
	for i in range(n):
		if a[i] != i:
			f = False
			break
	if len(s) != 0 or k < cnt or (not f):
		print(-1)
	else:
		print(cnt)
		print(ans, end='')
t = int(input())
while t:
	t -= 1
	solve()


def minSwaps(arr):
	n = len(arr)
	arrpos = [*enumerate(arr)]
	arrpos.sort(key=lambda it: it[1])
	vis = {k: False for k in range(n)}
	cycles = []
	for i in range(n):
		if vis[i] or arrpos[i][0] == i:
			continue
		j = i
		cycles.append([])
		while not vis[j]:
			cycles[-1].append(j)
			vis[j] = True
			j = arrpos[j][0]
	return cycles
t = int(input())
while t:
	(n, k_max) = map(int, input().split())
	seq = list(map(int, input().split()))
	opers = []
	cycles = minSwaps(seq)
	even_count = 0
	odd_count = 0
	for i in range(len(cycles)):
		if len(cycles[i]) % 2:
			odd_count += 1
		else:
			even_count += 1
	if even_count % 2 == 0:
		for i in range(len(cycles)):
			if len(cycles[i]) % 2:
				k = 0
				for _ in range(len(cycles[i]) // 2):
					opers.append([cycles[i][k + 2] + 1, cycles[i][k + 1] + 1, cycles[i][k] + 1])
					k += 2
			elif len(cycles[i]) > 2:
				k = 0
				for _ in range(len(cycles[i]) // 2 - 1):
					opers.append([cycles[i][k + 2] + 1, cycles[i][k + 1] + 1, cycles[i][k] + 1])
					k += 2
		jump = 0
		for i in range(len(cycles)):
			if len(cycles[i + jump]) % 2 == 0:
				for k in range(i + jump + 1, len(cycles)):
					if len(cycles[k]) % 2 == 0:
						opers.append([cycles[i + jump][-1] + 1, cycles[i + jump][-2] + 1, cycles[k][-2] + 1])
						opers.append([cycles[k][-1] + 1, cycles[k][-2] + 1, cycles[i + jump][-1] + 1])
						break
				jump += k - (i + jump)
			if i + jump >= len(cycles) - 1:
				break
		if len(opers) <= k_max:
			print(len(opers))
			for l in range(len(opers)):
				print(str(opers[l][0]) + ' ' + str(opers[l][1]) + ' ' + str(opers[l][2]))
	else:
		print('-1')
	t -= 1


def fun(l, ind, a, b, c):
	t = l[a]
	l[a] = l[c]
	ind[l[a]] = a
	l[c] = l[b]
	ind[l[c]] = c
	l[b] = t
	ind[l[b]] = b
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [0]
	n += 1
	a.extend(list(map(int, input().split())))
	ind = [i for i in range(0, n)]
	for i in range(n):
		ind[a[i]] = i
	ans = []
	a.append(n + 1)
	ind.append(n + 1)
	(c, i, p, q) = (0, 1, -1, -1)
	while i < n:
		if a[i] == i or q == i:
			i += 1
		else:
			if p == -1 and a[i] == ind[i]:
				(p, q) = (i, a[i])
				i += 1
				continue
			elif a[i] == ind[i]:
				ans.append([p, q, i])
				fun(a, ind, p, q, i)
				p = q = -1
				c += 1
				continue
			ans.append([i, a[i], ind[i]])
			fun(a, ind, i, a[i], ind[i])
			c += 1
			i += 1
		if c > k:
			break
	if p != -1 or k < c:
		print(-1)
		continue
	print(c)
	for j in range(c):
		print(ans[j][0], ans[j][1], ans[j][2])


def ans(lanth, arey, s):
	idx = {}
	for i in range(1, lanth + 1):
		idx[arey[i - 1]] = i
	isvisi = [False] * (lanth + 1)
	dicti = {}
	for i in range(lanth):
		dicti[i + 1] = arey[i]
	ckel = 1
	arey2 = []
	arey3 = []
	anval = 0
	anarey = []
	for k in range(1, lanth + 1):
		nxtnod = 0
		indarey = []
		if isvisi[k] == False:
			isvisi[k] = True
			if k == dicti[k]:
				continue
			else:
				c = dicti[k]
				indarey.append(k)
				while not isvisi[c]:
					isvisi[c] = True
					nxtnod = dicti[c]
					c = nxtnod
					ckel += 1
					indarey.append(idx[c])
				if ckel > 2:
					if ckel % 2 != 0:
						anval += ckel // 2
						c = 0
						tempi = []
						for i in indarey[::-1]:
							tempi.append(i)
							c += 1
							if c == 3:
								tempi.reverse()
								anarey.append(tempi)
								tempi = [i]
								c = 1
						ckel = 1
					else:
						tempi = []
						c = 0
						if len(arey2) != 0:
							anval += (ckel - 1) // 2
							for i in indarey[-1:0:-1]:
								tempi.append(i)
								c += 1
								if c == 3:
									tempi.reverse()
									anarey.append(tempi)
									tempi = [i]
									c = 1
							tempi = []
							tempi = arey2.pop()
							anval += 2
							anarey.append([tempi[1], indarey[0], indarey[1]])
							anarey.append([tempi[0], tempi[1], indarey[0]])
						elif len(arey3) != 0:
							tempi = []
							c = 0
							for i in indarey[-1:0:-1]:
								tempi.append(i)
								c += 1
								if c == 3:
									tempi.reverse()
									anarey.append(tempi)
									tempi = [i]
									anval += 1
									c = 1
							a = arey3.pop()
							tempi = []
							c = 0
							for i in a[-1:0:-1]:
								tempi.append(i)
								c += 1
								if c == 3:
									tempi.reverse()
									anarey.append(tempi)
									tempi = [i]
									anval += 1
									c = 1
							anval += 2
							anarey.append([a[1], indarey[0], indarey[1]])
							anarey.append([a[0], a[1], indarey[0]])
						else:
							arey3.append(indarey)
				elif ckel == 2:
					tempi = []
					if len(arey2) != 0:
						tempi = arey2.pop()
						anval += 2
						anarey.append([tempi[1], indarey[0], indarey[1]])
						anarey.append([tempi[0], tempi[1], indarey[0]])
					elif len(arey3) != 0:
						a = arey3.pop()
						tempi = []
						c = 0
						for i in a[-1:0:-1]:
							tempi.append(i)
							c += 1
							if c == 3:
								tempi.reverse()
								anarey.append(tempi)
								tempi = [i]
								anval += 1
								c = 1
						anval += 2
						anarey.append([a[1], indarey[0], indarey[1]])
						anarey.append([a[0], a[1], indarey[0]])
					else:
						arey2.append(indarey)
				ckel = 1
	if len(arey2) != 0 or len(arey3) != 0:
		print(-1)
	elif anval > k:
		print(-1)
	else:
		print(anval)
		for i in anarey:
			print(' '.join(map(str, i)))
tst = int(input())
for i in range(tst):
	z = input().split()
	m = int(z[0])
	r = int(z[1])
	arey = list(map(int, input().split()))
	ans(m, arey, r)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

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

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	(n, k) = get_ints()
	p = get_array()
	psort = sorted(p)
	f = 0
	for i in range(0, n):
		if p[i] != psort[i]:
			f = 1
			break
	ff = 0
	if psort == p[::-1]:
		ff = 1
	if f == 0:
		print(0)
	elif ff == 1:
		if n == 3:
			print(-1)
		elif n % 4 == 0 or n % 4 == 1:
			print(n // 2)
			i = 1
			j = n
			for k in range(n // 4):
				print(i, i + 1, n)
				print(i + 1, n, n - 1)
				i = i + 2
				n = n - 2
		else:
			print(-1)
	elif f == 1:
		sor = 0
		p.insert(0, 0)
		for i in range(1, n + 1):
			if p[i] != i:
				sor += 1
		count = 0
		ind = 0
		i = 1
		fin = []
		while i < n + 1:
			a = i
			b = p[i]
			if i == p[p[i]]:
				i += 1
				continue
			else:
				a = i
				b = p[i]
				c = p[p[i]]
				(p[a], p[b]) = (p[b], p[a])
				(p[a], p[c]) = (p[c], p[a])
				if p[a] == a:
					sor -= 1
				if p[b] == b:
					sor -= 1
				if p[c] == c:
					sor -= 1
				count += 1
				fin.append([a, b, c])
			if count > k:
				ind = -1
				break
		i = 1
		while i:
			if sor > 0 and sor <= 2:
				ind = -1
				break
			else:
				a = i
				b = p[i]
				if a != b:
					for j in range(i, n + 1):
						if j != a and j != b and (p[j] != j):
							c = j
							(p[a], p[b]) = (p[b], p[a])
							(p[a], p[c]) = (p[c], p[a])
							count += 1
							if p[a] == a:
								sor -= 1
							if p[b] == b:
								sor -= 1
							if p[c] == c:
								sor -= 1
							fin.append([a, b, c])
							break
			if i == p[i]:
				if i == n:
					break
				else:
					i = i + 1
			if count > k:
				ind = -1
				break
		if ind == -1:
			print(-1)
		else:
			print(len(fin))
			for i in fin:
				print(*i)


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(graph, visited, node, parent, cycle):
	visited.add(node)
	cycle.append(node)
	if graph[node] == parent:
		return cycle
	else:
		return dfs(graph, visited, graph[node], parent, cycle)
t = int(input())
while t > 0:
	t = t - 1
	(n, k) = list(map(int, input().split()))
	nodes = list(map(int, input().split()))
	visited = set()
	graph = dict()
	vertices = []
	for i in range(1, n + 1):
		if not nodes[i - 1] == i:
			vertices.append(i)
	notInplace = len(vertices)
	for i in range(1, n + 1):
		graph[i] = nodes[i - 1]
	even_cycles = []
	even_2s_cycles = []
	odd_cycles = []
	for i in vertices:
		if not i in visited:
			c = dfs(graph, visited, i, i, [])
			if len(c) == 2:
				even_2s_cycles.append(c)
			elif len(c) % 2 == 0:
				even_cycles.append(c)
			else:
				odd_cycles.append(c)
	totalCycles = len(even_cycles) + len(odd_cycles) + len(even_2s_cycles)
	if notInplace % 2 == 0 and (not totalCycles % 2 == 0) or (not notInplace % 2 == 0 and totalCycles % 2 == 0):
		print(-1)
	else:
		totalMoves = 0
		for j in even_2s_cycles:
			totalMoves += len(j) // 2
		for j in even_cycles:
			totalMoves += len(j) // 2
		for j in odd_cycles:
			totalMoves += len(j) // 2
		if totalMoves <= k:
			print(totalMoves)
			for j in odd_cycles:
				for v in range(0, len(j) - 2, 2):
					print('{} {} {}'.format(j[0], j[v + 1], j[v + 2]))
			for j in even_cycles:
				for v in range(0, len(j) - 2, 2):
					print('{} {} {}'.format(j[0], j[v + 1], j[v + 2]))
				even_2s_cycles.append([j[0], j[len(j) - 1]])
			for j in range(0, len(even_2s_cycles), 2):
				print('{} {} {}'.format(even_2s_cycles[j][0], even_2s_cycles[j][1], even_2s_cycles[j + 1][0]))
				print('{} {} {}'.format(even_2s_cycles[j + 1][1], even_2s_cycles[j + 1][0], even_2s_cycles[j][0]))