You are asked to sort \(A_1, A_2, \ldots,A_N\) in lexicographical order. This can be solved with a data structure called Trie.

Construct a Trie with the keys being \(A_1, \ldots, A_N\). Here, the same sequence should be corresponded to a single node. If a parent node \(v\) has a child node with value \(x_i\), reuse that node; otherwise, construct a new node \(u\) and add an edge \(v\stackrel{x_i}{\longrightarrow} u\). The children is managed in an associative array (like map in C++ or dict in Python). Each node also stores the indices of the corresponding sequences.

The answer can be found by performing a DFS (Depth-First Search) on this Trie. If a node has multiple edges, visit them in ascending order of their values. During the DFS, every time you visit a node, add the indices of the sequences corresponding to the node to the answer array in ascending order.

import sys

sys.setrecursionlimit(300100)

n = int(input())
G = [{} for i in range(n + 1)]
vs = [[] for i in range(n + 1)]
pos = [-1] * (n + 1) # Which node does sequence A_i belong to?
pos[0] = 0
tmp = 1
for i in range(1, n + 1):
    p, y = map(int, input().split())
    if y not in G[pos[p]]:
        G[pos[p]][y] = tmp
        tmp += 1
    pos[i] = G[pos[p]][y]
    vs[pos[i]].append(i)

ans = []


def dfs(i):
    global ans
    ans += vs[i]
    for j in sorted(list(G[i].keys())):
        dfs(G[i][j])


dfs(0)
print(*ans)