Encode the tree

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2220
64-bit integer IO format: %I64d      Java class name: Main

Description

Given n labeled vertices, there are nn-2 different trees. The number is too large, but Wiskey want to use a way to encode the tree that make a unique sequence associated with the labeled tree.

Follow this way:
1.Select the vertex u which degree is 1 and the labeled number is the minimum. Example, u = 4.
2.Select the neighbor v of u, exists the edge which u to v. Example, v = 1.
3.Delete the edge from the tree. Example, the edge of 1-4 will be deleting.
4.Repeat the first step, until only two vertices left.
5.We will get the sequence {u1, u2… un-2} and {v1, v2… vn-2}.
Now, give you the v sequence, tell me the u sequence.

Input

First line will contain one integer mean how many cases will follow by.
N represents the number of vertices, and the label start from 1. (3 <= N <= 100).
The next N-2 numbers mean the v sequence.

Output

Output the u sequence in one line, separate by a blank space.

Sample Input

1
8
1 2 1 3 3 5

Sample Output

4 6 2 1 7 3
Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .