Problem H
Chopping Wood
Given an unrooted tree structure as in the picture below, we chop it into pieces in the following way: pick the smallest numbered leaf, and remove the edge connecting that leaf to the tree. Then repeat this process until nothing is left of the tree.
![\includegraphics[width=0.8\textwidth ]{tree}](/problems/chopwood/file/statement/en/img-0001.png)
To record this process, we write list the edges of the tree in the order they were chopped off, and write each edge as “u v” where u is the leaf and v is its connecting vertex. So for the figure above we get:
u v 3 5 4 1 5 1 1 2 6 2 2 7
Unfortunately, we lost the first column of data of this extremely important list so we only have the “v” column. Can you help us reconstruct the “u” column? The vertices of the tree are always numbered from 1 up to the number of vertices.
Input
The first line of input contains an integer
Output
If the u column can be uniquely
determined, write
Warning
This problem has somewhat large amounts of input and output. We recommend you to make sure that your output is properly buffered, otherwise your solution may be too slow.
Sample Input 1 | Sample Output 1 |
---|---|
6 5 1 1 2 2 7 |
3 4 5 1 6 2 |
Sample Input 2 | Sample Output 2 |
---|---|
2 1 2 |
Error |