Code the Tree

A tree (a connected graph with no cycles) has its vertices numbered with the integers $1, 2, \ldots, n$. The Prufer code of such a tree is built as follows:

• Take the leaf (a vertex incident to exactly one edge) with the smallest number.
• Remove this leaf together with its incident edge, and write down the number of the vertex that was adjacent to it.
• Repeat this procedure on the remaining graph until only one vertex is left (this vertex always has number $n$).

The resulting sequence of $n - 1$ written-down numbers is the Prufer code of the tree.

Your task is to compute the Prufer code of a given tree. A tree is described by a word of the language defined by the following grammar:

T ::= "(" N S ")"
S ::= " " T S
    | empty
N ::= number

That is, a tree is surrounded by parentheses and begins with a number denoting the identifier of its root vertex, followed by arbitrarily many (possibly zero) subtrees, each separated by a single space character.

Note that, by this definition, the root of a tree may itself be a leaf. Choosing a root is only a matter of notation; what we are really dealing with is an unrooted tree.

The input contains several test cases. Each test case describes one tree, written as above, on a single line. Input is terminated by end of file. You may assume that $1 \le n \le 50$.

For each test case, print a single line containing the Prufer code of the given tree. Separate consecutive numbers with a single space, and do not print any trailing space at the end of a line. When $n = 1$ the code is empty, so print an empty line for that test case.