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 翻译