AT_arc209_d.[ARC209D] A_A_i

给定一个长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$，每个元素要么是 $1$ 到 $N$ 之间的整数（包含 $1$ 和 $N$），要么是 $-1$。

Snuke 决定用这个序列 $A$ 创建一个新序列。

首先，将序列 $A$ 中所有的 $-1$ 替换成 $1$ 到 $N$ 之间的某个整数（包含 $1$ 和 $N$）。

接着，根据如下公式创建长度为 $N$ 的序列 $B = (B_1, B_2, \ldots, B_N)$：

• $B_i = A_{A_i}$

请你找出字典序最小的可能的序列 $B$。

有 $T$ 组测试数据。请你分别求解每组数据。

什么是序列的字典序？如果存在整数 $1 \leq i \leq N$，使得满足以下两个条件，则序列 $C = (C_1, C_2, \ldots, C_N)$ 字典序小于 序列 $D = (D_1, D_2, \ldots, D_N)$：

• $(C_1, C_2, \ldots, C_{i-1}) = (D_1, D_2, \ldots, D_{i-1})$
• $C_i$ 在数值上小于 $D_i$。

输入按如下格式给出：

T
case_1
case_2
⋮
case_T

每组测试数据按如下格式给出：

N A_1 A_2 … A_N

对于每组测试数据，输出字典序最小的可能序列 $B$，每组测试数据占一行。

样例解释 1

在第一个测试用例中，Snuke 替换之前的序列 $A$ 为 $(4, -1, -1, 3)$。

假设他将其替换为 $A = (4, 3, 1, 3)$。

则 $B = (A_4, A_3, A_1, A_3) = (3, 1, 4, 1)$。

无法得到字典序更小的序列 $B$ 了。

约束条件

• $1 \leq T \leq 10^5$
• $1 \leq N \leq 5 \times 10^5$
• $1 \leq A_i \leq N$ 或 $A_i = -1$
• 所有测试数据中 $N$ 的总和不超过 $5 \times 10^5$
• 所有输入值均为整数。

由 ChatGPT 5 翻译