트리 복원하기

사이클이 없는 연결 그래프인 트리가 있고, 정점에는 정수 $1, 2, \ldots, n$ 이 번호로 매겨져 있다. 이 트리의 "프뤼퍼(Prüfer) 코드"는 다음과 같이 만든다. 먼저 잎(간선 하나에만 연결된 정점) 중 번호가 가장 작은 것을 고른다. 이 잎과 거기에 연결된 간선을 함께 제거하고, 그 잎과 이웃하던 정점의 번호를 기록한다. 남은 그래프에서 이 과정을 정점이 하나만 남을 때까지 반복한다(마지막에 남는 정점은 항상 $n$ 번이다). 이렇게 기록된 $n - 1$ 개의 수열이 그 트리의 프뤼퍼 코드이다.

주어진 프뤼퍼 코드로부터 트리를 복원하여라. 트리는 다음 문법으로 생성되는 언어의 단어로 표기한다.

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

즉, 트리는 괄호로 감싼다. 여는 괄호, 루트 정점의 번호, 그 뒤에 임의 개수(0개일 수도 있음)의 부분 트리를 각각 공백 하나로 구분하여 붙이고, 마지막에 닫는 괄호를 둔다.

트리는 루트가 없는 트리이므로 같은 트리를 나타내는 단어가 여러 개일 수 있다. 그래서 유일한 정규 표기 하나를 정한다(출력 참고). 루트로 지정한 정점 자체가 잎일 수도 있음에 유의하여라. 루트를 정하는 것은 트리를 적기 위한 편의일 뿐이며, 실제로 다루는 대상은 루트가 없는 트리이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 트리의 프뤼퍼 코드를 담는다. 즉 공백 하나로 구분된 $n - 1$ 개의 수가 주어진다($n = 1$ 이면 빈 줄이다). 입력은 파일 끝(EOF)에서 종료된다. $1 \le n \le 50$ 이라고 가정해도 된다.

각 테스트 케이스마다, 복원한 트리의 정규 표기를 한 줄에 출력하여라. 답을 유일하게 만들기 위해, 트리를 정점 $n$ 에 루트를 두고, 모든 정점에서 그 부분 트리들을 루트 정점 번호가 작은 순서로 나열한다. 정확히 말하면, 정점 $v$ 를 루트로 하는 부분 트리의 표기는 다음과 같다. 여는 괄호, 번호 $v$, 그다음 $v$ 의 각 자식 $c$ 에 대해 번호가 작은 순서대로 공백 하나와 $c$ 를 루트로 하는 부분 트리의 표기를 이어 붙이고, 마지막에 닫는 괄호를 둔다.

프뤼퍼 코드의 마지막 수는 항상 $n$ 이다. 코드를 만들 때와 똑같이, 현재 잎인 정점 중 가장 작은 것을 반복해서 이어 붙이면 트리를 복원할 수 있다.