Decode the Tree

A tree (a connected graph without cycles) has its vertices numbered with the integers $1, 2, \ldots, n$. The "Prüfer" code of such a tree is built as follows: take the leaf (a vertex incident to only 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 resulting graph until only one vertex is left (which is always vertex $n$). The written sequence of $n - 1$ numbers is the Prüfer code of the tree.

Your task is to reconstruct a tree from its Prüfer code. A tree is written as a word of the language generated by the following grammar:

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

That is, a tree is enclosed in parentheses: an opening parenthesis, the number identifying the root vertex, then arbitrarily many (possibly zero) subtrees, each preceded by a single space, and finally a closing parenthesis.

Because the tree is unrooted, many words describe the same tree, so we fix a single canonical word (see Output). Note that the vertex chosen as the root may itself be a leaf; designating a root is only a convenience for writing the tree down, since the object really being described is an unrooted tree.

The input contains several test cases. Each test case gives the Prüfer code of a tree on a single line: $n - 1$ numbers separated by single spaces (an empty line when $n = 1$). The input is terminated by end of file. You may assume $1 \le n \le 50$.

For each test case, print on a single line the canonical word for the reconstructed tree. To make the answer unique, root the tree at vertex $n$ and, at every vertex, order its subtrees by increasing root vertex number. Formally, the word for the subtree rooted at vertex $v$ is: an opening parenthesis, the number $v$, then for each child $c$ of $v$ in increasing order a single space followed by the word for the subtree rooted at $c$, and finally a closing parenthesis.

The last number of any Prüfer code is always $n$. Reconstruct the tree by repeatedly attaching the smallest vertex that is currently a leaf, mirroring how the code was produced.