Tree Grafting

Trees have many applications in computer science. Perhaps the most commonly used trees are rooted binary trees, but other kinds of rooted trees can be useful as well. One example is ordered trees, in which the subtrees of any given node are ordered. The number of children of each node is variable, and there is no upper limit on it. Formally, an ordered tree is a finite set of nodes $T$ such that

• one node is designated as the root, written root($T$);
• the remaining nodes are partitioned into subsets $T_1, T_2, \ldots, T_m$, each of which is itself a tree (a subtree).

We also define root($T_1$), ..., root($T_m$) to be the children of root($T$), with root($T_i$) being the $i$-th child. The nodes root($T_1$), ..., root($T_m$) are siblings.

It is often more convenient to represent an ordered tree as a rooted binary tree, so that every node can be stored in the same amount of memory. The conversion uses the following steps:

1. remove every edge from each node to its children;
2. for each node, add an edge to its first child in $T$ (if any) as the left child;
3. for each node, add an edge to its next sibling in $T$ (if any) as the right child.

This is illustrated below.

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

In most cases the height of the tree (the number of edges on the longest root-to-leaf path) increases after the conversion. This is undesirable, because the running time of many tree algorithms depends on the height.

Write a program that computes the height of the tree before and after the conversion.

The input consists of several lines, each describing the directions taken during a depth-first traversal of one tree; there is one line per tree. For example, the tree shown above is described by dudduduudu, meaning "0 down to 1, 1 up to 0, 0 down to 2, ...": d means moving down to a child and u means moving back up to the parent. The input is terminated by a line whose first character is #. Each tree has at least 2 and at most 10000 nodes.

For each tree, print the height of the tree before and after the conversion described above, using the format

Tree t: h1 => h2

where $t$ is the case number (starting from 1), $h_1$ is the height before the conversion and $h_2$ is the height after the conversion.