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

In Xiao Y's binary tree models, each node has a unique ID. Xiao Y hangs her favorite binary tree model on the wall, with the root at the top, and the left and right subtrees hanging below the root to the left and right, respectively, such that they also satisfy this hanging rule. To make the model more aesthetically pleasing, Xiao Y chooses a hanging method that minimizes the inorder traversal sequence of the binary tree. A "minimal inorder traversal" means the lexicographically smallest sequence of node IDs obtained from an inorder traversal.

One day, the model accidentally fell to the ground. Fortunately, all nodes and edges remained intact, but she cannot remember how the model was originally hung—that is, she cannot remember the ID of the root node.

Xiao Y has been busy preparing for the Tsinghua training camp and does not have much time to deal with other matters, so she has asked you, who are equally clever, to help restore her binary tree model.

Description

Given Xiao Y's binary tree model with nodes labeled $1$ to $n$, you need to provide the lexicographically smallest possible inorder traversal to help Xiao Y set up her model more quickly.

Input

The input is read from standard input.

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

This is followed by $n$ lines, each containing several integers:

The first integer on the $(i+1)$-th line is $k_i$, representing the degree of the node with ID $i$, followed by $k_i$ integers $a_{i,j}$, representing 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

The output is written to standard output.

Output a single line containing $n$ integers, representing the lexicographically smallest inorder traversal.

Examples

Input 1

4
3 2 3 4
1 1
1 1
1 1

Output 1

2 1 3 4

Note 1

One optimal solution for the example is as follows:

In this configuration, node 4 is the root, node 1 is the left child of node 4, and nodes 2 and 3 are the left and right children of node 1, respectively.

Constraints

There are 20 test cases in total, each worth 5 points. The data ranges for each test case are as follows:

The random data generation methods are as follows:

For test case 13, starting from a tree with two nodes, repeatedly pick a random node in the tree with degree 1 (i.e., a leaf node) and generate two new nodes directly connected to it, until the tree has $n$ nodes. Clearly, in this test case, $n$ is an even number.

For test cases 15 and 16, starting from a tree with one node, repeatedly pick a random node in the tree with a degree of at most 2 and generate one new node directly connected to it, until the tree has $n$ nodes.

Note

We provide a program binary_sample.cpp that only contains input and output functionality.

Instructions for this program can be found in readme.txt.

You may use the code from this program during the contest, or you may choose not to; this will not affect your score.