AT_abc437_e [ABC437E] Sort Arrays

$ 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 $ より（数として）小さい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ \vdots $ $ x_N $ $ y_N $

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

### Sample Explanation 1 $ A_1 = (2), A_2 = (1), A_3 = (1, 2), A_4 = (1) $ なので $ P=(2,4,3,1) $ です。 ### Sample Explanation 2 $ A_1 = A_2 = A_3 = A_4 = A_5 = (1) $ です。 ### Constraints - $ 1\leq N\leq 3\times 10^5 $ - $ 0\leq x_i\lt i $ - $ 1\leq y_i\leq 10^9 $ - 入力は全て整数