Every December, VK traditionally holds an event for its employees named "Secret Santa". Here's how it happens.

$n$ employees numbered from $1$ to $n$ take part in the event. Each employee $i$ is assigned a different employee $b_i$, to which employee $i$ has to make a new year gift. Each employee is assigned to exactly one other employee, and nobody is assigned to themselves (but two employees may be assigned to each other). Formally, all $b_i$ must be distinct integers between $1$ and $n$, and for any $i$, $b_i \ne i$ must hold.

The assignment is usually generated randomly. This year, as an experiment, all event participants have been asked who they wish to make a gift to. Each employee $i$ has said that they wish to make a gift to employee $a_i$.

Find a valid assignment $b$ that maximizes the number of fulfilled wishes of the employees.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). Description of the test cases follows.

Each test case consists of two lines. The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of participants of the event.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$; $a_i \ne i$) — wishes of the employees in order from $1$ to $n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print two lines.

In the first line, print a single integer $k$ ($0 \le k \le n$) — the number of fulfilled wishes in your assignment.

In the second line, print $n$ distinct integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le n$; $b_i \ne i$) — the numbers of employees assigned to employees $1, 2, \ldots, n$.

$k$ must be equal to the number of values of $i$ such that $a_i = b_i$, and must be as large as possible. If there are multiple answers, print any.


-----Examples-----

Input
2
3
2 1 2
7
6 4 6 2 4 5 6
Output
2
3 1 2
4
6 4 7 2 3 5 1


-----Note-----

In the first test case, two valid assignments exist: $[3, 1, 2]$ and $[2, 3, 1]$. The former assignment fulfills two wishes, while the latter assignment fulfills only one. Therefore, $k = 2$, and the only correct answer is $[3, 1, 2]$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Constructive algorithms

Greedy algorithms

Flows and cuts

Mathematics


Solutions:
import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	w = [False] * (n + 1)
	b = [None] * n
	for i in range(n):
		j = a[i]
		if not w[j]:
			w[j] = True
			b[i] = j
	c = []
	for i in range(1, n + 1):
		if not w[i]:
			c.append(i)
	for i in range(n):
		j = b[i]
		if j is None:
			if c[-1] != i + 1:
				b[i] = c.pop()
			elif len(c) != 1:
				c.pop()
				b[i] = c.pop()
				c.append(i + 1)
			else:
				v = a[i]
				for j in range(n):
					if b[j] == v:
						b[j] = i + 1
						b[i] = a[i]
						break
	r = 0
	for i in range(n):
		r += a[i] == b[i]
	print(r)
	print(' '.join(map(str, b)))
for i in range(int(input())):
	solve()


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

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

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
inf = 10 ** 16
md = 10 ** 9 + 7
from collections import Counter

def solve():
	n = II()
	aa = LI1()
	frm = [[] for _ in range(n)]
	for (i, a) in enumerate(aa):
		frm[a].append(i)
	ans = [-1] * n
	vac = []
	over = []
	k = 0
	for i in range(n):
		if len(frm[i]) == 0:
			vac.append(i)
		elif len(frm[i]) == 1:
			ans[frm[i][0]] = i + 1
			k += 1
		else:
			over.append(i)
	for a in vac:
		j = over[-1]
		if frm[j][-1] == a:
			i = frm[j].pop(-2)
		else:
			i = frm[j].pop()
		ans[i] = a + 1
		if len(frm[j]) == 1:
			i = frm[j].pop()
			ans[i] = j + 1
			over.pop()
			k += 1
	print(k)
	print(*ans)
for testcase in range(II()):
	solve()


import sys
from collections import defaultdict
input = lambda : sys.stdin.readline().strip()
intput = lambda : map(int, input().split())

def solve():
	(N,) = intput()
	A = [0] + list(intput())
	ans = [-1] * (N + 1)
	spare = []
	cnt = defaultdict(int)
	for x in A:
		cnt[x] += 1
	for i in range(1, N + 1):
		if i not in cnt:
			spare += [i]
	K = N - len(spare)
	for i in range(1, N + 1):
		if cnt[A[i]] > 1:
			x = spare.pop()
			if x == i:
				spare += [x]
				ans[i] = A[i]
			else:
				ans[i] = x
				cnt[A[i]] -= 1
		else:
			ans[i] = A[i]
	return (K, ans[1:])
(T,) = intput()
for _ in range(T):
	(k, s) = solve()
	print(k)
	print(*s)


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

def f(a):
	st = set([i for i in range(1, len(a) + 1)])
	g = {}
	for i in range(len(a)):
		if a[i] in st:
			st.remove(a[i])
		if a[i] not in g:
			g[a[i]] = [i]
		else:
			g[a[i]].append(i)
	ans = [0] * len(a)
	lt = list(st)
	j = 0
	for i in g:
		ans[g[i][0]] = i
		for ind in range(1, len(g[i])):
			id = g[i][ind]
			ans[id] = lt[j]
			j += 1
			if ans[id] == id + 1:
				(ans[id], ans[g[i][ind - 1]]) = (ans[g[i][ind - 1]], ans[id])
	cnt = 0
	for i in range(len(ans)):
		if a[i] == ans[i]:
			cnt += 1
	print(cnt)
	return ans
for i in range(int(input())):
	n = input()
	a = list(map(int, input().strip().split()))
	print(*f(a))


from sys import stdin
input = stdin.readline
rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip()
YN = lambda x: print('YES') if x else print('NO')
mod = 10 ** 9 + 7
for _ in range(rn()):
	n = rn()
	a = rl()
	ans = len(set(a))
	pans = [-1 for i in range(n)]
	s = set(range(1, n + 1))
	ms = s.copy()
	gives = s.copy()
	for i in range(n):
		if a[i] in s:
			s.remove(a[i])
	for num in s:
		if a[num - 1] in ms:
			gives.remove(num)
			ms.remove(a[num - 1])
			pans[num - 1] = a[num - 1]
	for i in range(n):
		if a[i] in ms:
			gives.remove(i + 1)
			pans[i] = a[i]
			ms.remove(a[i])
	gives = list(gives)
	ms = list(ms)
	if len(gives) > 0:
		if gives[0] == ms[0]:
			(gives[0], gives[1]) = (gives[1], gives[0])
		for i in range(len(gives)):
			if gives[i] != ms[i]:
				pans[gives[i] - 1] = ms[i]
			else:
				pans[gives[i - 1] - 1] = ms[i]
				pans[gives[i] - 1] = ms[i - 1]
				(ms[i], ms[i - 1]) = (ms[i - 1], ms[i])
	print(ans)
	print(*pans)


from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	b = [0] * n
	c = [0] * n
	check = [False] * n
	check[a[0] - 1] = True
	b[0] = a[0]
	for i in range(1, n):
		if not check[a[i] - 1]:
			check[a[i] - 1] = True
			b[i] = a[i]
	for i in range(n):
		if b[i] != 0:
			c[b[i] - 1] = i
	cnt = n - b.count(0)
	p = []
	for i in range(n):
		if not check[i]:
			p.append(i + 1)
	j = 0
	for i in range(n - 1, -1, -1):
		if b[i] == 0:
			b[i] = p[j]
			if b[i] == i + 1:
				b[i] = a[i]
				b[c[a[i] - 1]] = p[j]
			j += 1
	print(cnt)
	for i in b:
		print(i, end=' ')
	print()


import math
import heapq
import string
from collections import deque
import sys
input = sys.stdin.readline
S = lambda : input()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
H = 1000000000 + 7
for _ in range(I()):
	n = I()
	l = L()
	(g, r, di) = ([0] * n, [0] * n, {})
	for i in range(n):
		if r[l[i] - 1] == 0:
			g[i] = 1
			di[i] = l[i] - 1
			r[l[i] - 1] = 1
	print(len(di))
	(l1, l2) = ([], [])
	for i in range(n):
		if g[i] == 0:
			l1.append(i)
		if r[i] == 0:
			l2.append(i)
	p = len(l1) - 1
	for i in range(p + 1):
		if l1[i] == l2[i]:
			if i != p:
				(l1[i], l1[p]) = (l1[p], l1[i])
			else:
				(l1[0], l1[p]) = (l1[p], l1[0])
	for i in range(p + 1):
		di[l1[i]] = l2[i]
	if len(l1) == 1 and l1[0] == l2[0]:
		di[l1[0]] = l[l1[0]] - 1
		for i in range(n):
			if l[i] == l[l1[0]] and i != l1[0]:
				di[i] = l1[0]
				break
	for i in range(n):
		print(di[i] + 1, end=' ')
	print()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = [0] + list(map(int, input().split()))
	b = [0 for i in range(n + 1)]
	c = []
	d = []
	for i in range(1, n + 1):
		if b[a[i]] == 0:
			b[a[i]] = i
		else:
			c.append(i)
	for i in range(1, n + 1):
		if b[i] == 0:
			d.append(i)
	for i in range(len(c)):
		if c[i] == d[i]:
			y = c[i]
			x = b[a[y]]
			b[a[y]] = y
			c[i] = x
		b[d[i]] = c[i]
	an = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		an[b[i]] = i
	o = 0
	for i in range(1, n + 1):
		if a[i] == an[i]:
			o += 1
	print(o)
	print(*an[1:])


from collections import *
from math import *
from sys import stdin
input = stdin.readline
T = int(input())
for case in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [-1] * n
	l1 = list(Counter(a).keys())
	l2 = list(range(1, n + 1))
	l = list(set(l2) - set(l1))
	d = {}
	count = 0
	for i in range(n):
		if a[i] not in d:
			d[a[i]] = i
			ans[i] = a[i]
			count += 1
		else:
			ans[i] = l.pop()
	for i in range(n):
		if ans[i] == i + 1:
			(ans[d[a[i]]], ans[i]) = (ans[i], a[i])
			d[a[i]] = i
	print(count)
	print(*ans)


for i in range(int(input())):
	n = int(input())
	a = [int(j) for j in input().split()]
	mapping = {j: 0 for j in range(1, n + 1)}
	rem = []
	b = []
	cnt = 0
	for j in a:
		mapping[j] += 1
	for j in mapping.keys():
		if mapping[j] == 0:
			rem.append(j)
	for j in range(len(a)):
		if len(rem) == 0:
			break
		elif mapping[a[j]] > 1 and rem[-1] != j + 1:
			mapping[a[j]] -= 1
			a[j] = rem[-1]
			rem.pop()
			cnt += 1
	print(n - cnt)
	print(*a)


for i in range(int(input())):
	n = int(input())
	a = [int(j) for j in input().split()]
	mapping = [0] * (n + 1)
	rem = []
	b = []
	cnt = 0
	for j in a:
		mapping[j] += 1
	for j in range(1, n + 1):
		if mapping[j] == 0:
			rem.append(j)
	for j in range(len(a)):
		if mapping[a[j]] > 1 and len(rem) and (rem[-1] != j + 1):
			b.append(rem[-1])
			rem.pop()
			mapping[a[j]] -= 1
		else:
			b.append(a[j])
			cnt += 1
	print(cnt)
	print(*b)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = [0] * (n + 1)
	rem = []
	for k in a:
		cnt[k] += 1
	for i in range(1, n + 1):
		if cnt[i] == 0:
			rem.append(i)
	b = []
	tmp = 0
	for i in range(n):
		if cnt[a[i]] > 1 and rem and (rem[-1] != i + 1):
			b.append(rem[-1])
			rem.pop()
			cnt[a[i]] -= 1
		else:
			b.append(a[i])
			tmp += 1
	print(tmp)
	print(*b)


def solve(n, a):
	ans = [0] * (n + 1)
	taken = [0] * (n + 1)
	stack = []
	count = 0
	for i in range(1, n + 1):
		ans[i] = a[i]
		taken[a[i]] += 1
	for i in range(1, n + 1):
		if taken[i] == 0:
			stack.append(i)
			count += 1
	print(n - count)
	for i in range(1, n + 1):
		if taken[a[i]] == 1:
			continue
		if len(stack) == 0:
			break
		top = stack[-1]
		if i != top:
			taken[a[i]] -= 1
			ans[i] = top
			stack.pop()
	ans.pop(0)
	return ans
for _ in range(int(input())):
	n = int(input())
	a = [0] + list(map(int, input().split()))
	print(*solve(n, a))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0] * n
	ungifted = []
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	for i in range(1, n + 1):
		if i not in d:
			ungifted.append(i)
	z = len(ungifted)
	for i in range(n):
		if d[a[i]] > 1:
			x = ungifted.pop()
			if x == i + 1:
				ungifted.append(x)
				ans[i] = a[i]
			else:
				ans[i] = x
				d[a[i]] -= 1
		else:
			ans[i] = a[i]
	print(n - z)
	print(*ans)


def solve(n, a):
	unsat = set(range(1, n + 1))
	fixed = 0
	voulait = 0
	nb = 0
	for i in range(n):
		if a[i] in unsat:
			nb += 1
			unsat.remove(a[i])
		else:
			a[i] = -a[i]
	for i in range(n):
		retire = 0
		if a[i] < 0:
			if i + 1 in unsat:
				if len(unsat) > 1:
					retire = 1
					unsat.remove(i + 1)
				else:
					fixed = i + 1
					voulait = -a[i]
			a[i] = unsat.pop()
			if retire:
				unsat.add(i + 1)
	if not fixed:
		print(nb)
		print(*a)
		return
	iv = a.index(voulait)
	(a[iv], a[fixed - 1]) = (a[fixed - 1], a[iv])
	print(nb)
	print(*a)
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	solve(n, a)


from collections import defaultdict
t = int(input())
for i in range(1, t + 1):
	n = int(input())
	ls = list(map(int, input().split()))
	dic = defaultdict(list)
	for (idx, item) in enumerate(ls, 1):
		dic[item].append(idx)
	to_fill = []
	for idx in range(1, n + 1):
		if idx not in dic:
			to_fill.append(idx)
	if not to_fill:
		print(n)
		print(' '.join(map(str, ls)))
	else:
		dups = []
		for key in dic:
			if len(dic[key]) > 1:
				dups.append(key)
		dups_idx = 0
		for item in to_fill:
			popped = dic[dups[dups_idx]].pop()
			if item == popped:
				temp = dic[dups[dups_idx]][-1]
				dic[dups[dups_idx]][-1] = popped
				popped = temp
			ls[popped - 1] = item
			if len(dic[dups[dups_idx]]) == 1:
				dups_idx += 1
		print(n - len(to_fill))
		print(' '.join(map(str, ls)))


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	cnt = [0 for _ in range(n + 1)]
	rem = []
	for i in a:
		cnt[i] += 1
	for i in range(1, n + 1):
		if cnt[i] == 0:
			rem.append(i)
	ans = []
	for i in range(n):
		if cnt[a[i]] > 1 and rem and (rem[-1] != i + 1):
			ans.append(rem.pop())
			cnt[a[i]] -= 1
		else:
			ans.append(a[i])
	print(len(set(a)))
	print(*ans)
	t = t - 1


from collections import deque
I = lambda : map(int, input().split())

def solve(a):
	n = len(a)
	ans = [0] * n
	ungifted = []
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	for i in range(1, n + 1):
		if i not in d:
			ungifted.append(i)
	z = len(ungifted)
	for i in range(n):
		if d[a[i]] > 1:
			x = ungifted.pop()
			if x == i + 1:
				ungifted.append(x)
				ans[i] = a[i]
			else:
				ans[i] = x
				d[a[i]] -= 1
		else:
			ans[i] = a[i]
	print(n - z)
	print(*ans)
t = int(input())
while t:
	t -= 1
	n = int(input())
	A = list(I())
	solve(A)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = a.copy()
	k = 0
	employee = set(range(1, n + 1))
	for i in range(n):
		if b[i] in employee:
			employee.remove(b[i])
			k += 1
		else:
			b[i] = -1
	for i in range(n):
		if b[i] == -1:
			e1 = employee.pop()
			if e1 != i + 1:
				b[i] = e1
			elif len(employee) != 0:
				e2 = employee.pop()
				employee.add(e1)
				b[i] = e2
			else:
				b[i] = a[i]
				aux = a[i]
				for j in range(n):
					if i != j and b[j] == aux:
						b[j] = e1
						break
	print(k)
	print(*b, sep=' ')
	print()


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

def rot1(seq):
	it = iter(seq)
	first = next(seq)
	yield from it
	yield first

def reorder(part, whole):
	yield from part
	yield from (whole - part)

def solve():
	n = int(input())
	receives = dict()
	for (i, ai) in enumerate(readline()):
		ai -= 1
		if ai not in receives:
			receives[ai] = i
		else:
			wish = ai
	no_gift = set(range(n)) - set(receives.keys())
	sad = set(range(n)) - set(receives.values())
	k = len(receives)
	if k == n - 1 and sad == no_gift:
		x = sad.pop()
		sad.add(receives.pop(wish))
		receives[wish] = x
	b = [None] * n
	for (j, i) in receives.items():
		b[i] = j + 1
	loop = no_gift & sad
	if k < n:
		for (j, i) in zip(rot1(reorder(loop, no_gift)), reorder(loop, sad)):
			b[i] = j + 1
	assert all((v is not None for v in b))
	print(k)
	print(*b)

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


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = set(a)
	c = set(a)
	ans = []
	numb = []
	for j in range(1, n + 1):
		if j in b:
			b.remove(j)
		else:
			numb.append(j)
	print(len(set(a)))
	pntr = 0
	cnt = 0
	d = {}
	for elem in a:
		if elem in c:
			ans.append(elem)
			d[elem] = cnt
			c.remove(elem)
		else:
			ans.append(numb[pntr])
			d[numb[pntr]] = cnt
			pntr += 1
		cnt += 1
	for j in range(len(ans)):
		if ans[j] == j + 1:
			v1 = d[a[j]]
			(ans[j], ans[v1]) = (ans[v1], ans[j])
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	res = [0] * n
	temp = [0] * (n + 1)
	b = [False] * (n + 1)
	count = 0
	for i in range(n):
		if a[i] != i + 1:
			if not b[a[i]]:
				count += 1
				res[i] = a[i]
				temp[a[i]] = i
				b[a[i]] = True
	ind = 1
	i = n - 1
	while i >= 0:
		if res[i] == 0:
			while b[ind]:
				ind += 1
			if ind == i + 1:
				b[ind] = True
				res[i] = a[i]
				res[temp[a[i]]] = ind
				continue
			res[i] = ind
			b[ind] = True
		i -= 1
	print(count)
	for i in res:
		print(i, end=' ')
	print('')


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	ans = [0] * n
	remain = set([i for i in range(1, n + 1)])
	dic = {}
	idx = 0
	for i in arr:
		if i in dic:
			dic[i].append(idx)
		else:
			dic[i] = [idx]
		idx += 1
	count = 0
	for i in range(n):
		if arr[i] in remain:
			ans[i] = str(arr[i])
			remain.remove(arr[i])
			count += 1
	remain = list(remain)
	for i in range(n):
		if ans[i] == 0:
			temp = remain.pop()
			if i + 1 == temp:
				ans[i] = str(arr[i])
				for idx in dic[arr[i]]:
					if idx != i:
						ans[idx] = str(temp)
						break
			else:
				ans[i] = str(temp)
	print(count)
	print(' '.join(ans))


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr = [0] + arr
	pt = [0] * (n + 1)
	graph = [[] for i in range(n + 1)]
	for i in range(1, n + 1):
		pt[i] = arr[i]
		graph[arr[i]].append(i)
	a = []
	b = []
	for i in range(1, n + 1):
		if len(graph[i]) < 1:
			a.append(i)
		if len(graph[i]) > 1:
			b.append(i)
	while len(a):
		x = a.pop()
		l = graph[b[-1]]
		y = l.pop()
		if y == x:
			yy = l.pop()
			l.append(y)
			y = yy
		graph[x].append(y)
		pt[y] = x
		if len(graph[b[-1]]) == 1:
			b.pop()
	ans = 0
	for i in range(1, n + 1):
		if arr[i] != pt[i]:
			ans = ans + 1
	print(n - ans)
	print(*pt[1:])


from collections import deque
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) - 1 for x in input().split()]
	d = dict()
	mapp = [-1] * n
	s = set([i for i in range(n)])
	happy = 0
	for a in range(n):
		if arr[a] in s:
			d[arr[a] + 1] = a
			mapp[a] = arr[a] + 1
			happy += 1
			s.remove(arr[a])
	left = deque(s)
	for a in range(n):
		if mapp[a] == -1:
			tmp = left.pop()
			if a == tmp and len(left) == 0:
				sw = d[arr[a] + 1]
				(mapp[sw], mapp[a]) = (mapp[a], mapp[sw])
				mapp[sw] = tmp + 1
			elif a == tmp:
				tmp2 = left.pop()
				mapp[a] = tmp2 + 1
				left.append(tmp)
			else:
				mapp[a] = tmp + 1
	print(happy)
	print(*mapp)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = [0] * (n + 1)
	ans = [0] * (n + 1)
	anss = 0
	t = 1
	for i in range(n):
		if l1[l[i]] == 0:
			ans[i + 1] = l[i]
			l1[l[i]] = 1
			anss += 1
	ex = []
	for i in range(1, n + 1):
		if l1[i] == 0:
			ex.append(i)
	for i in range(1, n + 1):
		if ans[i] == 0:
			if ex[-1] == i:
				if len(ex) == 1:
					t = 0
					cc = i
					xx = ex[-1]
					break
				z = ex.pop()
				ans[i] = ex[-1]
				ex.pop()
				ex.append(z)
			else:
				ans[i] = ex[-1]
				ex.pop()
	if t == 0:
		kk = 0
		xxx = l[cc - 1]
		for i in range(1, n + 1):
			if l[i - 1] == xxx:
				ans[cc] = xxx
				ans[i] = cc
				kk = 1
				break
		if kk == 0:
			for i in range(1, n + 1):
				if ans[i] != l[i - 1] and i != cc:
					ans[cc] = ans[i]
					ans[i] = cc
					break
	print(anss)
	for i in range(1, n + 1):
		print(ans[i], end=' ')
	print()


t = int(input())
for task in range(t):
	n = int(input())
	wishes = list(map(int, input().split()))
	resSanta = [0] * n
	targets = []
	for i in range(n):
		targets.append([])
	res = n
	for i in range(n):
		targets[wishes[i] - 1].append(i)
	curLost = 0
	curTarget = 0
	while curLost < n and curTarget < n:
		while curLost < n and len(targets[curLost]) != 0:
			curLost += 1
		while curTarget < n and len(targets[curTarget]) < 2:
			curTarget += 1
		if curLost >= n or curTarget >= n:
			break
		res -= 1
		if curLost == targets[curTarget][-1]:
			targets[curLost].append(targets[curTarget].pop(0))
		else:
			targets[curLost].append(targets[curTarget].pop())
	for i in range(n):
		resSanta[targets[i][0]] = i + 1
	print(res)
	for i in range(n):
		print(resSanta[i], end=' ')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	a = [0] * (n + 1)
	for i in range(n):
		a[arr[i] - 1] = 1
	b = [0] * n
	k = 0
	for i in range(n):
		if a[i] == 0:
			b[k] = i + 1
			k += 1
	c = [0] * n
	result = [0] * n
	tt = 0
	j = 0
	kk = 0
	for i in range(n):
		if c[arr[i] - 1] == 0:
			result[i] = arr[i]
			c[arr[i] - 1] = i + 1
			j += 1
		elif b[tt] == i + 1:
			result[i] = arr[i]
			result[c[arr[i] - 1] - 1] = b[tt]
			c[arr[i] - 1] = i + 1
			tt += 1
		else:
			result[i] = b[tt]
			tt += 1
	print(j)
	for i in range(n):
		print(result[i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	d = [-1] * (n + 1)
	v = {i: 0 for i in range(n + 1)}
	k = 0
	temp = {}
	for i in l:
		if i in temp:
			continue
		else:
			temp[i] = 1
			k += 1
	t = {}
	for i in range(n):
		if v[l[i]] == 0:
			v[l[i]] = 1
			d[i + 1] = l[i]
			t[l[i]] = i + 1
	s = []
	for i in v:
		if v[i] == 0 and i != 0:
			s.append(i)
	s.sort()
	idx = 0
	for i in range(1, n + 1):
		if d[i] == -1:
			can = s[idx]
			if i != can:
				d[i] = s[idx]
				idx += 1
			else:
				p = t[l[i - 1]]
				(d[i], d[p]) = (l[i - 1], s[idx])
				(t[l[i - 1]], t[i]) = (i, p)
				idx += 1
	print(k)
	for i in range(1, n + 1):
		print(d[i], end=' ')
	print()


from collections import defaultdict as dd

def solve(A, n):
	ans = [0] * (n + 1)
	up = set(range(1, n + 1))
	down = set(range(1, n + 1))
	inc = dd(list)
	k = 0
	for i in range(1, n + 1):
		ai = A[i - 1]
		inc[ai].append(i)
		if ai in down:
			down.remove(ai)
			up.remove(i)
			ans[i] = ai
			k += 1
	In = up.intersection(down)
	U = list(In) + list(up.difference(In))
	D = list(In) + list(down.difference(In))
	ln = len(U)
	if ln == 1 and U[0] == D[0]:
		comm = A[U[0] - 1]
		i = inc[comm][0]
		ans[i] = D[0]
		ans[U[0]] = comm
	else:
		for (i, it) in enumerate(U):
			ans[it] = D[(i + 1) % ln]
	print(k)
	print(*ans[1:])
for case in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	ans = solve(A, n)