AT_abc437_e [ABC437E] Sort Arrays

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 $ .

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 $ P_1, P_2, \ldots, P_N $ in one line, separated by spaces.

### Sample Explanation 1 $ A_1 = (2), A_2 = (1), A_3 = (1, 2), A_4 = (1) $ , so $ 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 $ - All input values are integers.