트리 부호화

정수 $1, 2, \ldots, n$ 으로 정점에 번호가 매겨진 트리(사이클이 없는 연결 그래프)가 주어진다. 이 트리의 프뤼퍼(Prufer) 코드는 다음과 같이 만든다.

• 번호가 가장 작은 잎(정확히 하나의 간선에만 연결된 정점)을 고른다.
• 이 잎과 그에 연결된 간선을 함께 제거하고, 그 잎과 인접해 있던 정점의 번호를 기록한다.
• 남은 그래프에서 정점이 하나만 남을 때까지 이 과정을 반복한다(마지막에 남는 정점의 번호는 항상 $n$ 이다).

이렇게 기록된 $n - 1$ 개의 수열이 이 트리의 프뤼퍼 코드이다.

주어진 트리의 프뤼퍼 코드를 계산하여라. 트리는 다음 문법으로 정의되는 언어의 문자열로 표현된다.

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

즉, 트리는 괄호로 둘러싸이며, 먼저 루트 정점의 번호를 나타내는 수가 오고, 그 뒤에 임의 개수(0개일 수도 있음)의 서브트리가 각각 하나의 공백 문자로 구분되어 이어진다.

이 정의에 따르면 트리의 루트 자체가 잎일 수도 있다. 루트를 정하는 것은 표기의 편의를 위한 것일 뿐이며, 실제로 다루는 것은 뿌리 없는(unrooted) 트리이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 위 형식으로 표현된 하나의 트리를 한 줄에 담고 있다. 입력은 파일의 끝(EOF)에서 종료된다. $1 \le n \le 50$ 임을 가정해도 좋다.

각 테스트 케이스마다 해당 트리의 프뤼퍼 코드를 한 줄에 출력한다. 수와 수 사이는 하나의 공백으로 구분하며, 줄 끝에는 공백을 출력하지 않는다. $n = 1$ 인 경우 코드가 비어 있으므로 해당 테스트 케이스에는 빈 줄을 출력한다.