Given a permutation $a_1, a_2, \dots, a_n$ of integers from $1$ to $n$, and a threshold $k$ with $0 \leq k \leq n$, you compute a sequence $b_1, b_2, \dots, b_n$ as follows.

For every $1 \leq i \leq n$ in increasing order, let $x = a_i$.

If $x \leq k$, set $b_{x}$ to the last element $a_j$ ($1 \leq j < i$) that $a_j > k$. If no such element $a_j$ exists, set $b_{x} = n+1$.

If $x > k$, set $b_{x}$ to the last element $a_j$ ($1 \leq j < i$) that $a_j \leq k$. If no such element $a_j$ exists, set $b_{x} = 0$.

Unfortunately, after the sequence $b_1, b_2, \dots, b_n$ has been completely computed, the permutation $a_1, a_2, \dots, a_n$ and the threshold $k$ are discarded.

Now you only have the sequence $b_1, b_2, \dots, b_n$. Your task is to find any possible permutation $a_1, a_2, \dots, a_n$ and threshold $k$ that produce the sequence $b_1, b_2, \dots, b_n$. It is guaranteed that there exists at least one pair of permutation $a_1, a_2, \dots, a_n$ and threshold $k$ that produce the sequence $b_1, b_2, \dots, b_n$.

A permutation of integers from $1$ to $n$ is a sequence of length $n$ which contains all integers from $1$ to $n$ exactly once.


-----Input-----

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 10^5$), indicating the length of the permutation $a$.

The second line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \leq b_i \leq n+1$), indicating the elements of the sequence $b$.

It is guaranteed that there exists at least one pair of permutation $a_1, a_2, \dots, a_n$ and threshold $k$ that produce the sequence $b_1, b_2, \dots, b_n$.

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


-----Output-----

For each test case, output the threshold $k$ ($0 \leq k \leq n$) in the first line, and then output the permutation $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$) in the second line such that the permutation $a_1, a_2, \dots, a_n$ and threshold $k$ produce the sequence $b_1, b_2, \dots, b_n$. If there are multiple solutions, you can output any of them.


-----Examples-----

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


-----Note-----

For the first test case, permutation $a = [1,3,2,4]$ and threshold $k = 2$ will produce sequence $b$ as follows.

When $i = 1$, $x = a_i = 1 \leq k$, there is no $a_j$ ($1 \leq j < i$) that $a_j > k$. Therefore, $b_1 = n + 1 = 5$.

When $i = 2$, $x = a_i = 3 > k$, the last element $a_j$ that $a_j \leq k$ is $a_1$. Therefore, $b_3 = a_1 = 1$.

When $i = 3$, $x = a_i = 2 \leq k$, the last element $a_j$ that $a_j > k$ is $a_2$. Therefore, $b_2 = a_2 = 3$.

When $i = 4$, $x = a_i = 4 > k$, the last element $a_j$ that $a_j \leq k$ is $a_3$. Therefore, $b_4 = a_3 = 2$.

Finally, we obtain sequence $b = [5,3,1,2]$.

For the second test case, permutation $a = [1,2,3,4,5,6]$ and threshold $k = 3$ will produce sequence $b$ as follows.

When $i = 1, 2, 3$, $a_i \leq k$, there is no $a_j$ ($1 \leq j < i$) that $a_j > k$. Therefore, $b_1 = b_2 = b_3 = n + 1 = 7$.

When $i = 4, 5, 6$, $a_i > k$, the last element $a_j$ that $a_j \leq k$ is $a_3$. Therefore, $b_4 = b_5 = b_6 = a_3 = 3$.

Finally, we obtain sequence $b = [7,7,7,3,3,3]$.

For the third test case, permutation $a = [6,5,4,3,2,1]$ and threshold $k = 3$ will produce sequence $b$ as follows.

When $i = 1, 2, 3$, $a_i > k$, there is no $a_j$ ($1 \leq j < i$) that $a_j \leq k$. Therefore, $b_4 = b_5 = b_6 = 0$.

When $i = 4, 5, 6$, $a_i \leq k$, the last element $a_j$ that $a_j > k$ is $a_3$. Therefore, $b_1 = b_2 = b_3 = a_3 = 4$.

Finally, we obtain sequence $b = [4,4,4,0,0,0]$.

Source: codeforces | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms

Tree algorithms

Spanning trees

Data structures


Solutions:
import sys
from collections import deque
input = sys.stdin.readline

def solve():
	n = int(input())
	par = [-1 for _ in range(n + 2)]
	child = [[] for _ in range(n + 2)]
	degree = [0] * (n + 2)
	B = list(map(int, input().split()))
	rg = [0, n]
	for i in range(n):
		if B[i] > i + 1:
			rg[0] = max(rg[0], i + 1)
		elif B[i] < i + 1:
			rg[1] = min(rg[1], i)
		par[i + 1] = B[i]
		degree[B[i]] += 1
		child[B[i]].append(i + 1)
	root = 1
	while par[root] >= 0:
		root = par[root]
	ans = []
	q = deque([root])
	while q:
		node = q.popleft()
		if 1 <= node <= n:
			ans.append(node)
		tmp = []
		for ch in child[node]:
			if degree[ch] == 0:
				q.append(ch)
			else:
				tmp.append(ch)
		while tmp:
			q.append(tmp.pop())
	print(rg[0])
	print(*ans)
	return
for _ in range(int(input())):
	solve()


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	b = list(map(int, inp().split()))
	g = [[] for i in range(n + 2)]
	for i in range(n):
		g[b[i]].append(i + 1)
	d = [-1] * (n + 2)
	q = [0, n + 1]
	res = []
	if len(g[0]):
		f = 1
	else:
		f = 0
	M = n + 5
	m = 0
	while q:
		q.sort(key=lambda x: len(g[x]))
		res += q
		qn = []
		for x in q:
			for v in g[x]:
				if d[v] < 0:
					d[v] = d[x] + 1
					qn.append(v)
					if f == 1:
						M = min(M, v)
					else:
						m = max(m, v)
		f ^= 1
		q = qn
	print(m)
	print(' '.join(map(str, res[2:])))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


t = int(input())
for i in range(t):
	n = int(input())
	w = [int(k) for k in input().split()]
	for j in range(n):
		if w[j] < j + 1:
			k = j
			break
	else:
		k = n
	q = {}
	for j in range(n):
		if w[j] in q:
			q[w[j]].append(j + 1)
		else:
			q[w[j]] = [j + 1]
	new = []
	z = n + 1
	if z in q:
		while True:
			new.append([])
			new[-1] = q[z]
			for j in new[-1]:
				if j in q:
					z = j
					new[-1][new[-1].index(z)] = new[-1][-1]
					new[-1][-1] = z
					break
			else:
				break
	z = 0
	if z in q:
		while True:
			new.append([])
			new[-1] = q[z]
			for j in new[-1]:
				if j in q:
					z = j
					new[-1][new[-1].index(z)] = new[-1][-1]
					new[-1][-1] = z
					break
			else:
				break
	delta = []
	for j in new:
		delta.extend(j)
	print(k)
	print(' '.join([str(k) for k in delta]))


m = int(input())
for _ in range(m):
	n = int(input())
	b = [0] + [int(x) for x in input().split()]
	seg = [0, n + 1]
	for i in range(1, len(b)):
		left = min(i, b[i])
		right = max(i, b[i])
		seg[0] = max(seg[0], left)
		seg[1] = min(seg[1], right)
		if seg[1] - seg[0] == 1:
			break
	k = seg[0]
	print(k)
	dic = {}
	for i in range(1, len(b)):
		if b[i] in dic:
			dic[b[i]].append(i)
		else:
			dic[b[i]] = [i]
	now = 0 if 0 in dic else n + 1
	while True:
		tem = -1
		for j in dic[now]:
			if j not in dic:
				print(j, end=' ')
			else:
				tem = j
		if tem == -1:
			break
		now = tem
		print(now, end=' ')
	print()