트리 접붙이기

트리는 컴퓨터 과학에서 다양하게 쓰인다. 가장 흔히 쓰이는 것은 루트 있는 이진 트리이지만, 다른 종류의 루트 트리도 유용할 수 있다. 그 예로 순서 트리(ordered tree) 가 있는데, 이 트리에서는 각 노드의 부분 트리들에 순서가 매겨져 있다. 각 노드의 자식 수는 정해져 있지 않으며 상한도 없다. 형식적으로, 순서 트리는 다음을 만족하는 유한한 노드 집합 $T$ 로 이루어진다.

• 한 노드가 루트로 지정되며, 이를 root($T$) 로 나타낸다.
• 나머지 노드들은 부분집합 $T_1, T_2, \ldots, T_m$ 으로 분할되고, 각 부분집합 역시 하나의 트리(부분 트리)이다.

또한 root($T_1$), ..., root($T_m$) 을 root($T$) 의 자식으로 정의하며, root($T_i$) 가 $i$ 번째 자식이다. root($T_1$), ..., root($T_m$) 은 서로 형제(sibling)이다.

모든 노드를 같은 크기의 공간에 저장할 수 있도록, 순서 트리를 루트 있는 이진 트리로 표현하는 것이 더 편리한 경우가 많다. 변환은 다음 단계로 이루어진다.

1. 각 노드에서 자식으로 가는 간선을 모두 제거한다.
2. 각 노드에 대해, $T$ 에서의 첫 번째 자식(있다면)으로 가는 간선을 왼쪽 자식으로 추가한다.
3. 각 노드에 대해, $T$ 에서의 다음 형제(있다면)로 가는 간선을 오른쪽 자식으로 추가한다.

아래 그림이 이 과정을 보여 준다.

         0                             0
       / | \                          /
      1  2  3       ===>             1
        / \                           \
       4   5                           2
                                      / \
                                     4   3
                                      \
                                       5

대부분의 경우 변환 후 트리의 높이(루트에서 잎까지의 경로 중 가장 긴 것의 간선 수)가 늘어난다. 많은 트리 알고리즘의 수행 시간이 높이에 의존하므로 이는 바람직하지 않다.

변환 전과 변환 후의 트리 높이를 계산하는 프로그램을 작성하라.

입력은 여러 줄로 주어지며, 각 줄은 한 트리를 깊이 우선 순회(DFS)하면서 이동한 방향을 나타낸다. 트리 하나당 한 줄이다. 예를 들어 위 그림의 트리는 dudduduudu 로 표현되는데, 이는 "0에서 1로 내려가고, 1에서 0으로 올라오고, 0에서 2로 내려가고, ..." 를 뜻한다. 즉 d 는 자식으로 내려가는 것을, u 는 부모로 올라오는 것을 의미한다. 입력은 첫 글자가 # 인 줄로 끝난다. 각 트리의 노드 수는 2개 이상 10000개 이하이다.

각 트리에 대해, 위에서 설명한 변환 전과 변환 후의 트리 높이를 다음 형식으로 출력하라.

Tree t: h1 => h2

여기서 $t$ 는 (1부터 시작하는) 트리 번호, $h_1$ 은 변환 전 높이, $h_2$ 는 변환 후 높이이다.