D - A_A_i Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 900 点

問題文

長さ N の数列 A = (A_1, A_2, \ldots, A_N) が与えられます。 各要素は 1 以上 N 以下の整数もしくは -1 です。

すぬけ君はこの数列 A を用いて新しい数列を作ることにしました。

まず、この数列 A に登場する -1 を全て 1 以上 N 以下の整数に書き換えます。

次に、以下の式に従って長さ N の数列 B = (B_1, B_2, \ldots, B_N) を作ります。

  • B_i=A_{A_i}

B としてありうるもののうち辞書順で最小のものを求めてください。

T 個のテストケースが与えられるので、それぞれについて解いてください。

数列の辞書順とは？

数列 C = (C_1,C_2,\ldots,C_N) が数列 D = (D_1,D_2,\ldots,D_N) より辞書順で小さいとは、ある整数 1 \leq i \leq N が存在して、下記の 2 つがともに成り立つことを言います。

  • (C_1,C_2,\ldots,C_{i-1}) = (D_1,D_2,\ldots,D_{i-1})
  • C_i が D_i より（数として）小さい。

制約

  • 1 \le T \le 10^5
  • 1 \le N \le 5 \times 10^5
  • 1 \le A_i \le N または A_i = -1
  • すべてのテストケースにわたる N の総和は 5\times 10^5 以下
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

T
case_1
case_2
\vdots
case_T

各ケースは以下の形式で与えられる。

N
A_1 A_2 \dots A_N

出力

各テストケースに対する、B としてありうるもののうち辞書順で最小のものを改行区切りで出力せよ。

入力例 1

3
4
4 -1 -1 3
5
5 4 5 3 1
7
-1 6 5 -1 7 -1 6

出力例 1

3 1 4 1
1 3 1 5 5
1 1 7 1 6 1 1

1 番目のテストケースにおいて、すぬけ君が書き換える前の数列 A は (4,-1,-1,3) です。

すぬけ君が A=(4, 3, 1, 3) と書き換えたとします。

このとき、B=(A_4, A_3, A_1, A_3)=(3, 1, 4, 1) となります。

これよりも辞書順で小さい数列 B を得ることはできません。

Score : 900 points

Problem Statement

You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N. Each element is either an integer between 1 and N (inclusive) or -1.

Snuke has decided to create a new sequence using this sequence A.

First, replace all -1s in this sequence A with integers between 1 and N (inclusive).

Next, create a sequence B = (B_1, B_2, \ldots, B_N) of length N according to the following formula:

  • B_i=A_{A_i}

Find the lexicographically smallest possible sequence B.

You are given T test cases. Solve each of them.

What is the lexicographical order of sequences?

A sequence C = (C_1,C_2,\ldots,C_N) is lexicographically smaller than a sequence D = (D_1,D_2,\ldots,D_N) if and only if there exists an integer 1 \leq i \leq N such that both of the following hold:

  • (C_1,C_2,\ldots,C_{i-1}) = (D_1,D_2,\ldots,D_{i-1})
  • C_i is (numerically) smaller than D_i.

Constraints

  • 1 \le T \le 10^5
  • 1 \le N \le 5 \times 10^5
  • 1 \le A_i \le N or A_i = -1.
  • The sum of N over all test cases is at most 5\times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is given in the following format:

N
A_1 A_2 \dots A_N

Output

For each test case, output the lexicographically smallest possible sequence B, separated by newlines.

Sample Input 1

3
4
4 -1 -1 3
5
5 4 5 3 1
7
-1 6 5 -1 7 -1 6

Sample Output 1

3 1 4 1
1 3 1 5 5
1 1 7 1 6 1 1

In the first test case, the sequence A before Snuke's replacement is (4,-1,-1,3).

Suppose he replaces it to get A=(4, 3, 1, 3).

Then, B=(A_4, A_3, A_1, A_3)=(3, 1, 4, 1).

It is impossible to obtain a lexicographically smaller sequence B than this.