E - Sort Arrays Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

N+1 個の数列 A_0, A_1, \ldots, A_{N} があります。A_i は以下のように定義されます。

  • A_0 は空の数列
  • A_i\ (1\leq i\leq N) は数列 A_{x_i}\ (0\leq x_i\lt i) の末尾に整数 y_i を追加することで得られる数列

以下の条件を満たす (1,2,\ldots,N) の順列 P=(P_1, P_2,\ldots,P_N) を求めてください。

  • i = 1,2,\ldots,N-1 に対して、以下のいずれかが成り立つ。
    • A_{P_i} は辞書順で A_{P_{i+1}} より小さい。
    • A_{P_i}= A_{P_{i+1}} かつ P_i\lt P_{i+1}

言い換えると、A_1,A_2,\ldots,A_N を辞書順で小さいものから順に並べたとき（等しい列が複数ある場合には添え字が小さいものを先にするように並べる）、その並びに現れる添え字の列が P です。

数列の辞書順とは？

数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、|S|, |T| はそれぞれ S, T の長さを表します。

  1. |S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})。
  2. ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して、下記の 2 つがともに成り立つ。
    • (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
    • S_i が T_i より（数として）小さい。

制約

  • 1\leq N\leq 3\times 10^5
  • 0\leq x_i\lt i
  • 1\leq y_i\leq 10^9
  • 入力は全て整数

入力

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

N
x_1 y_1
x_2 y_2
\vdots
x_N y_N

出力

P_1, P_2, \ldots, P_N を空白区切りで一行で出力せよ。

入力例 1

4
0 2
0 1
2 2
0 1

出力例 1

2 4 3 1

A_1 = (2), A_2 = (1), A_3 = (1, 2), A_4 = (1) なので P=(2,4,3,1) です。

入力例 2

5
0 1
0 1
0 1
0 1
0 1

出力例 2

1 2 3 4 5

A_1 = A_2 = A_3 = A_4 = A_5 = (1) です。

入力例 3

10
0 305186313
1 915059758
0 105282054
1 696409999
3 185928366
3 573289179
6 254538849
3 105282054
5 696409999
8 168629803

出力例 3

3 8 10 5 9 6 7 1 4 2

Score : 450 points

Problem Statement

There are N+1 sequences A_0, A_1, \ldots, A_{N}. A_i is defined as follows:

  • A_0 is an empty sequence.
  • A_i\ (1\leq i\leq N) is a sequence obtained by appending an integer y_i to the end of the sequence A_{x_i}\ (0\leq x_i\lt i).

Find the permutation P=(P_1, P_2,\ldots,P_N) of (1,2,\ldots,N) that satisfies the following condition:

  • For i = 1,2,\ldots,N-1, one of the following holds:
    • A_{P_i} is lexicographically smaller than A_{P_{i+1}}.
    • A_{P_i}= A_{P_{i+1}} and P_i\lt P_{i+1}

In other words, when A_1,A_2,\ldots,A_N are arranged in lexicographical order (when there are multiple equal sequences, arrange those with smaller indices first), P is the sequence of indices that appears in that arrangement.

What is the lexicographical order of sequences?

A sequence S = (S_1,S_2,\ldots,S_{|S|}) is lexicographically smaller than a sequence T = (T_1,T_2,\ldots,T_{|T|}) if one of the following two conditions holds. Here, |S| and |T| represent the lengths of S and T, respectively.

  1. |S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
  2. There exists an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace such that both of the following hold:
    • (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
    • S_i is (numerically) smaller than T_i.

Constraints

  • 1\leq N\leq 3\times 10^5
  • 0\leq x_i\lt i
  • 1\leq y_i\leq 10^9
  • All input values are integers.

Input

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

N
x_1 y_1
x_2 y_2
\vdots
x_N y_N

Output

Output P_1, P_2, \ldots, P_N in one line, separated by spaces.

Sample Input 1

4
0 2
0 1
2 2
0 1

Sample Output 1

2 4 3 1

A_1 = (2), A_2 = (1), A_3 = (1, 2), A_4 = (1), so P=(2,4,3,1).

Sample Input 2

5
0 1
0 1
0 1
0 1
0 1

Sample Output 2

1 2 3 4 5

A_1 = A_2 = A_3 = A_4 = A_5 = (1).

Sample Input 3

10
0 305186313
1 915059758
0 105282054
1 696409999
3 185928366
3 573289179
6 254538849
3 105282054
5 696409999
8 168629803

Sample Output 3

3 8 10 5 9 6 7 1 4 2