Reconstructing Skew Heap Insertion Sequence

A skew heap is a variant of a binary heap. In a skew heap the heap‐order property holds: every non‐root node has a value greater than its parent, so the root always stores the minimum value. Unlike binary heaps, the left and right children in a skew heap have no ordering restrictions and the tree need not be balanced.

The insertion procedure for a skew heap is defined recursively as follows. Let H be a skew heap and let X be a new element (all elements are distinct). When inserting X into H:

• If H is empty or X is less than the root of H, then X becomes the new root and the old heap H becomes the left child of X (with no right child). In formula,\( insert(\varnothing, X)= Node(X,\varnothing,\varnothing) \) and if X < H.root then \[ insert(H, X)= Node(X, H, \varnothing). \]
• If X is greater than the root of H, then first swap the two children of H, and then recursively insert X into the new left subtree. That is, if X > H.root then \[ insert(H, X)= Node(H.root, insert(H', X), H'.right), \] where H' is obtained from H by swapping its two children.

In this problem you are given a skew heap T that contains every value from 0 to n exactly once. Your task is to find a permutation S (a sequence of n+1 integers) such that if you start with an empty heap and insert the elements of S one by one by the above procedure you obtain exactly the given heap T. If there are more than one possible sequence, output the lexicographically smallest one (compare element‐by‐element; the sequence with a smaller first differing element is considered smaller).

You may assume that the input guarantees at least one valid answer.

inputFormat

The input begins with an integer n (0 ≤ n ≤ 15) indicating that the heap contains n+1 nodes with the distinct integer values 0, 1, …, n. The next n+1 lines describe the nodes of the skew heap. Each line contains three space‐separated integers:

• value: the node’s value.
• l: the index of the left child, or -1 if there is no left child.
• r: the index of the right child, or -1 if there is no right child.

The nodes are numbered from 0 to n. It is guaranteed that the given tree is a valid skew heap and that exactly one node is not a child of any other node (i.e. the root).

outputFormat

Output a line with n+1 space‐separated integers representing the lexicographically smallest insertion sequence that produces the given skew heap.

sample

1
0 1 -1
1 -1 -1

0 1