MEX Tree

题目描述

Given positive integer $n$ and non-negative integer sequence $a_{1 \dots n}$.

You have to construct a rooted tree $T$ with $n$ nodes, labeld $1 \dots n$.

Let $d_i$ be the number of edges on the unique simple path between the root and node $i$ on tree $T$.

You need to maximize $m = \operatorname{MEX}\ \{ a_i+d_i \mid i=1 \dots n\}$, where $\operatorname{MEX} S$ is defined as the smallest non-negative integer that is not in set $S$.

You need to solve $C$ testcases for each test data.

输入格式

The first line of input contains a single integer $C$($1 \le C \le 2 \times 10^4$). Then $C$ testcases follows.

The first line of each testcase contains a single integer $n$($1 \le n \le 2 \times 10^5$).

The second line of each testcase contains $n$ integers $a_1,a_2,\dots,a_n$($0 \le a_n \le n$).

It is guaranteed that the sum of $n$ over all testcases in a single testdata does not exceed $2 \times 10^5$.

输出格式

For each testcase, you should output two lines.

The first line of each testcase contains one integer $m_{\max}$, the maximum $m$.

The second line of each testcase contains $n$ non-negative integers $f_1,f_2,\dots,f_n$. $f_i=0$ means that node $i$ is the root of $T$, otherwise $f_i$ is the label of the parent of node $i$ on $T$.

If there are several possible $T$s, you may output any of them.

样例输入 #1

3
3
0 2 0
7
1 0 4 1 0 2 6
1
1

样例输出 #1

2
0 1 1
6
2 0 2 1 2 1 2
0
0