New Year's '16 P4 - DIY Christmas Tree - Olympiads Online Judge

New Year's '16 P4 - DIY Christmas Tree

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 128M

Author:

Problem type

You have been mailed a disassembled Christmas tree. In the box, there were three things: a set of $N$ $N$ branches, a drawing of a tree with $N$ $N$ nodes in total, and a set of safety instructions.

Each branch can be attached to one other branch. The attachment relationship between two branches can be described as follows: if you attach a branch $x$ $x$ to another branch $y$ $y$ , $x$ $x$ is considered a child of $y$ $y$ . Each branch also has a distinct weight, which is represented by an integer from $1$ $1$ to $N$ $N$ .

The safety instructions state:

Every branch except the lightest branch should be attached to another branch.
Start by placing the lightest branch at the top of your tree.
Add all the remaining branches in a predetermined order, one at a time.
When adding a branch with a weight of $q$ $q$ , find the heaviest branch already added to the assembled tree which is strictly lighter than $q$ $q$ . Attach the $q$ $q$ weight branch to the one found. If the found branch already has children (attached branches), place it to the right side of all of its children.

Before you start, you realize that you must add the branches in a specific order so that the resulting tree will match the diagram's tree.

Input Specification

On the first line, read one integer $N$ $N$ . $1 \le N \le 50\,000$ $1 \leq N \leq 50 000$ holds for all cases, and $N \le 7$ $N \leq 7$ holds for 15% of the points.

The following $N$ $N$ lines depict an adjacency list of the diagram, where the $i^\text{th}$ $i^{th}$ line begins with a single integer $k$ $k$ denoting the number of children of node $i$ $i$ , where $0 \le k < N$ $0 \leq k < N$ . Following is a space, and $k$ $k$ more space separated integers on the same line. Each integer $w$ $w$ ( $1 \le w \le N$ $1 \leq w \leq N$ ) indicates that node $w$ $w$ is a child of $i$ $i$ .

It is guaranteed that the tree will be rooted at $1$ $1$ .

Please note that for the second section of input, the ordering of children matters. Values of $w$ $w$ are given from left to right, and the tree created by your program's output is to match this. Additionally, the values of $i$ $i$ should be considered meaningless other than to make reading the input easier. The diagram consists of branches which are unidentified other than by their position relative to other branches.

If you are still confused, please consult the sample input.

Output Specification

Print a permutation of the numbers in the range $[1,N]$ $[1, N]$ , such that the assembled tree matches the one given in the input. We assert that two trees match if, when simultaneously traversing both in a depth-first manner, the number of children contained by the $j^\text{th}$ $j^{th}$ branch in one tree is equal to the number of children contained by the $j^\text{th}$ $j^{th}$ branch of the other tree for all possible values of $j$ $j$ .

If there are multiple possible answers, output any one of them (only one).
If there is no answer, output a single integer $0$ $0$ .

Again, consult the samples for more clarification.

Sample Input 1

Copy

Sample Output 1

Copy

1 3 2

Explanation for Sample 1

The diagram's tree looks like this:

$\text{[math]}$

By starting with the branch with weight $1$ $1$ , then adding branch $3$ $3$ , you get this:

$\text{[math]}$

Now add the $2$ $2$ -weight branch:

$\text{[math]}$

You can see that the two trees are structurally equivalent. Remember, numbers don't matter.

In this case, the given answer is the only valid answer. For example, adding the branches in the order $1,2,3$ $1, 2, 3$ would produce a different tree:

$\text{[math]}$

Sample Input 2

Copy

Sample Output 2

Copy

1 2 5 6 3 7 4

Explanation for Sample 2

The tree looks like this:

$\text{[math]}$

As you can see, it probably works.

Comments

0

garmel commented on Jan. 2, 2016, 3:40 a.m.

Hi, is the second output right? Mustn't it be 1 2 5 6 7 3 4?

0

k_53P commented on Jan. 2, 2016, 3:41 a.m.

If you believe there are multiple possible answers, print any of them.

0

garmel commented on Jan. 2, 2016, 3:45 a.m.

thanks for answering, the output2 is the answer of the assembling shown below?

0

k_53P commented on Jan. 2, 2016, 3:48 a.m.

Yes, sample output 2 is correct. It produces the desired tree, as shown.