Code the Tree

Time Limit: Java: 2000 ms / Others: 2000 ms

Memory Limit: Java: 65536 KB / Others: 65536 KB


A tree (i.e. a connected graph without cycles) with vertices numbered bythe integers 1, 2, ..., n is given. The "Prufer" code ofsuch a tree is built as follows: the leaf (a vertex that is incident to onlyone edge) with the minimal number is taken. This leaf, together with itsincident edge is removed from the graph, while the number of the vertexthat was adjacent to the leaf is written down. In the obtained graph, thisprocedure is repeated, until there is only one vertex left (which, by theway, always has number n). The written down sequence of n-1numbers is called the Prufer code of the tree.
Your task is, given a tree, to compute its Prufer code. The tree is denotedby a word of the language specified by the following grammar:T ::= "(" N S ")"S ::= " " T S | emptyN ::= numberThat is, trees have parentheses around them, and a number denoting theidentifier of the root vertex, followed by arbitrarily many (maybe none)subtrees separated by a single space character. As an example, take alook at the tree in the figure below which is denoted in the first lineof the sample input.

Note that, according to the definition given above, the root of a treemay be a leaf as well. It is only for the ease of denotation that wedesignate some vertex to be the root. Usually, what we are dealing herewith is called an "unrooted tree".


The input contains several test cases. Each test case specifies a treeas described above on one line of the input file. Input is terminatedby EOF. You may assume that 1<=n<=50.


For each test case generate a single line containing the Prufer code ofthe specified tree. Separate numbers by a single space. Do not print anyspaces at the end of the line.

Sample Input

(2 (6 (7)) (3) (5 (1) (4)) (8))
(1 (2 (3)))
(6 (1 (4)) (2 (3) (5)))

Sample Output

5 2 5 2 6 2 8
2 3
2 1 6 2 6




University of Ulm Local Contest 2001