以下是Lhc在JSOI2008冬令营时给A班同学讲解的树的有关知识。 树结构在计算机科学中有着广泛的应用。可是平时使用最多的还是有根二叉树，但是一些其他种类的有根树也有着同样重要的应用。一个例子就是有序树，它的一个节点的子树是有序的，并且一个节点的孩子节点数是一个变数，没有上限。有序树包括一个有限节点集，其中有一个节点是根root(T)，剩余的节点分别属于m个集合T1,T2……Tm，每一个集合又都是一棵有序树的节点集，其中root(T1),root(T2)……root(Tm)分别是root(T)的第i个孩子节点。 通常情况下，将一棵有序树表述成二叉树处理问题会更加方便，我们可以这样进行转化： 1、删除所有的边； 2、对于每一个节点，从它向它的孩子（如果存在）连一条边作为其左孩子； 3、对于每一个节点，从它向它的下一个兄弟（如果存在）连一条边作为其右孩子。 以下为一个例子： 图片外网地址： [IMG]http://jsoi.jzhx.net/wxdfiles/24.jpg[/IMG] 图片内网地址 [IMG]http://192.168.21.227/wxdfiles/24.jpg[/IMG] 在绝大多数的情况下，树的高度都在转化后变大了。这点让人十分讨厌，因为许多算法的复杂度都与树的高度有关。 现在Lhc想看看你是否完全掌握了这一知识，他请你编写一个程序，计算转化前后树的高度。

输入文件graft.in包括多行（行数≤700），每一行以深度优先遍历的方式描述了一棵转化前的树。如上图所示的树可以表示为dudduduudu，意味着0向下到1，1向上到0，0向下到2…… 输入文件以一行单独的”#”结束。 你可以认为给定的树合法且节点数不少于2个，不多于10000个。

输出文件graft.out对于每一组数据，使用以下格式输出一行，表示树转化前后的高度： Tree t: h1=> h2 其中t是测试数据组数，从1开始编号，h1是转化前的高度，h2是转化后的高度。 注意：t之前、h1之前之后、h2之前均有一个空格，其它地方没有空格，区分大小写。

dudduduudu
ddddduuuuu
dddduduuuu
dddduuduuu
#

Tree 1: 2 => 4
Tree 2: 5 => 5
Tree 3: 4 => 5
Tree 4: 4 => 4