Description

Xiao Y is a handy OIer who owns many binary tree models.

In Xiao Y’s binary tree model, each node has an id. She hung her favorite binary tree model on the wall, with the root at the top, and the left and right subtrees placed at the lower-left and lower-right of the root, respectively; they all follow the same hanging rule recursively. To make the model more elegant, Xiao Y chose a hanging orientation that makes the inorder traversal sequence of this binary tree lexicographically smallest. “Lexicographically smallest” means the sequence of node ids visited by an inorder traversal is lexicographically minimal.

One day, the model accidentally fell to the ground. Fortunately, none of the nodes or edges were damaged, but she could no longer recall how the model had been hung; in other words, she forgot the id of the root node.

Recently, Xiao Y has been busy preparing for the Tsinghua training, so she doesn’t have much time for other things. She turns to you for help to restore her binary tree model.

Input Format

The first line contains a positive integer $n$, the number of nodes.

Then follow $n$ lines, each containing several integers:

In the $(i + 1)$-th line, the first integer is $k_i$, the degree of node $i$, followed by $k_i$ integers $a_{i, j}$, indicating that there is an edge between node $i$ and node $a_{i, j}$.

Adjacent elements on the same line are separated by exactly one space.

Output Format

Output a single line with $n$ integers: the lexicographically smallest inorder traversal.

4
3 2 3 4
1 1
1 1
1 1

2 1 3 4

Hint

Subtasks

This problem has $20$ test points, each worth $5$ points. Constraints for each test point are as follows:

The random testdata are generated as follows: For the $13$-th test point, start from a tree with two nodes. Each time, pick a node of degree $1$ (i.e., a leaf) uniformly at random and attach two new nodes to it, until the tree has $n$ nodes. Clearly, in this test point, $n$ is even. For the $15$-th and $16$-th test points, start from a tree with one node. Each time, pick a node whose degree does not exceed $2$ uniformly at random and attach one new node to it, until the tree has $n$ nodes.

Hint

We provide a program binary_sample.cpp that only handles input and output. See readme.txt for details. You may use the code of this program when solving the problem, or not; this will not affect your score.

Translated by ChatGPT 5