Podboq 박사, 혹은: 우리는 어떻게 비대칭이 되었는가

유명한 생물학자 Podboq 박사는 생물의 배아가 발생 과정에서 어떻게 비대칭이 되는지를 오랫동안 연구한 끝에 새로운 가설에 도달했다. 그는 곧 열릴 학술 대회를 위한 포스터를 준비하고 있다. 이 포스터에는 하나의 세포에서 시작해 세포 분열을 반복하며 배아가 발생하는 과정을 나타내는 트리가 그려져 있다. 여러분이 할 일은, 청중이 아이디어를 더 쉽게 이해할 수 있도록 주어진 트리를 특정 조건을 만족하는 형태로 변환하는 프로그램을 작성하는 것이다.

세포 분열 과정을 나타내는 트리는 아래와 같은 형태이다.

• 시작 세포는 맨 위에 원으로 그린다.
• 각 세포는 분열을 멈추거나, 정확히 두 개의 세포로 분열한다. 따라서 각 세포(원)에서 아래로 내려가는 가지는 없거나, 두 자식 세포로 이어지는 두 개의 가지가 있다.

(그림 F-1은 그러한 트리의 한 예이다.)

Podboq 박사의 가설에 따르면, 이 트리의 구조를 보고 어떤 세포가 더 강하거나 약한 비대칭성을 가지는지 판단할 수 있다. 먼저 가설은 세포의 좌우 유사도를 다음과 같이 정의한다.

1. 더 이상 분열하지 않은 세포의 좌우 유사도는 $0$이다.
2. 분열한 세포에 대해서는, 그 세포의 자식 세포와 자손 세포 각각을 뿌리로 하는 부분 트리들을 모아, 그중 서로 다른 구조가 몇 가지 나타나는지를 센다. 이 세포의 좌우 유사도는, 왼쪽 자식 쪽과 오른쪽 자식 쪽 양쪽 모두에서 나타나는 구조의 개수를, 나타나는 서로 다른 구조의 전체 개수로 나눈 비율로 정의한다. 어떤 두 트리는, 임의로 고른 몇몇 세포의 두 자식 세포를 서로 맞바꿔서 완전히 같은 모양으로 만들 수 있으면 같은 구조로 본다.

예를 들어 아래 트리를 생각해 보자.

(그림 F-2: 예시 트리.)

세포 A의 좌우 유사도는 다음과 같이 계산한다. A의 왼쪽 자식인 세포 B의 자손들 안에서는 서로 다른 세 가지 구조가 나타난다. 그중 마지막 구조는 세 번 나타나지만, 구조의 종류를 셀 때는 한 번만 센다는 점에 유의하라.

(그림 F-3은 B의 자손들 안에서 나타나는 구조들이다.)

A의 오른쪽 자식인 세포 C의 자손들 안에서는 서로 다른 네 가지 구조가 나타난다.

(그림 F-4는 C의 자손들 안에서 나타나는 구조들이다.)

B 쪽의 첫째, 둘째, 셋째 구조는 각각 C 쪽의 둘째, 셋째, 넷째 구조와 같다. 따라서 전체 서로 다른 구조는 네 가지이고, 그중 세 가지가 왼쪽과 오른쪽에 공통으로 나타난다. 즉 A의 좌우 유사도는 $3/4$이다.

모든 세포의 좌우 유사도가 주어지면, 가설은 다음 규칙으로 두 세포 X와 Y 중 어느 쪽이 더 강한 비대칭성을 가지는지 결정한다.

1. X와 Y의 좌우 유사도가 다르면, 좌우 유사도가 더 낮은 쪽이 더 강한 비대칭성을 가진다.
2. 그렇지 않고 X와 Y 모두 자식 세포가 없으면, 둘은 완전히 같은 비대칭성을 가진다.
3. 그렇지 않으면 X와 Y는 모두 두 자식 세포를 가진다. X의 두 자식 중 더(또는 같게) 비대칭인 자식과 Y의 두 자식 중 더(또는 같게) 비대칭인 자식을 비교하여, 그 자식이 더 강한 비대칭성을 가지는 쪽이 더 강한 비대칭성을 가진다.
4. 그래도 동점이면, X의 남은(덜 비대칭인) 자식과 Y의 남은 자식을 비교하여, 그 자식이 더 강한 비대칭성을 가지는 쪽이 더 강한 비대칭성을 가진다.
5. 그래도 동점이면, X와 Y는 완전히 같은 비대칭성을 가진다.

위 규칙에서 자식 세포를 비교할 때는 같은 규칙을 재귀적으로 적용한다.

여러분이 할 일은, 주어진 세포 분열 트리를 오직 몇몇 세포의 두 자식 세포를 맞바꾸는 연산만으로 변환하여, 다음 조건을 만족하는 트리로 만드는 것이다.

1. 트리의 시작 세포이거나 어떤 부모 세포의 왼쪽 자식인 모든 세포 X에 대해: X가 두 자식 세포를 가지면, 왼쪽 자식이 오른쪽 자식보다 더 강하거나 같은 비대칭성을 가져야 한다.
2. 어떤 부모 세포의 오른쪽 자식인 모든 세포 X에 대해: X가 두 자식 세포를 가지면, 오른쪽 자식이 왼쪽 자식보다 더 강하거나 같은 비대칭성을 가져야 한다.

두 자식 세포의 비대칭성이 같은 경우에는 어느 순서든 같은 모양의 트리가 되므로 순서는 상관없다.

예를 들어 주어진 트리가 그림 F-2라고 하자. 먼저 B와 C를 비교하면, B의 좌우 유사도가 더 낮아 더 강한 비대칭성을 가지므로 B를 왼쪽에, C를 오른쪽에 둔다. 다음으로 B는 A의 왼쪽 자식이므로, B의 두 자식은 더 비대칭인 쪽이 왼쪽에 오도록 배치한다. C는 A의 오른쪽 자식이므로, C의 두 자식은 더 비대칭인 쪽이 오른쪽에 오도록 배치한다. 나머지 모든 세포도 같은 방식으로 처리하면, 트리는 최종적으로 아래와 같은 결과로 변환된다.

(그림 F-5는 변환 후의 예시 트리이다.)

변환 과정에서 허용되는 유일한 연산은 어떤 부모 세포의 두 자식 세포를 맞바꾸는 것뿐임에 유의하라. 예를 들어 그림 F-2의 트리를 그림 F-6과 같은 트리로 변환하는 것은 허용되지 않는다.

입력은 각각 하나의 트리를 나타내는 $n$개의 줄($1 \le n \le 100$)로 이루어지며, 마지막에는 입력의 끝을 나타내는, 오직 하나의 $0$만 있는 줄이 온다. 각 트리는 최소 $1$개, 최대 $127$개의 세포를 가진다. 아래는 트리 표현의 한 예이다.

((x (x x)) x)

이 표현은 그림 F-1의 트리를 나타낸다. 좀 더 정확히 말하면, 트리의 표현은 다음 두 형식 중 하나이다.

"(" <왼쪽 자식 트리의 표현> <공백 한 칸> <오른쪽 자식 트리의 표현> ")"

또는

"x"

앞의 형식은 시작 세포가 두 자식 세포를 가지는 트리의 표현이고, 뒤의 형식은 시작 세포가 자식 세포를 가지지 않는 트리의 표현이다.

입력의 각 트리에 대해, 변환 후의 트리를 나타내는 한 줄을 출력한다. 출력에서 트리는 입력과 같은 형식으로 표현하며, 표현들은 입력과 같은 순서로 출력한다. 각 줄에는 트리 표현 하나만 있어야 하고 그 외의 문자가 있어서는 안 된다.