描述
有一组作业，记为$x_1, x_2, \ldots, x_n$，需要被调度。每个作业需要一天完成。你的任务是调度这些作业，使它们能在最少的天数内完成。有两种约束条件：冲突约束和优先约束。

冲突约束：某些作业对不能在同一天完成。（例如作业$x_i$和作业$x_j$需要使用同一台机器，因此它们必须在不同的日期完成）。

优先约束：对于某些作业对，一个作业必须在另一个作业完成后才能开始。例如，作业$x_i$不能在作业$x_j$完成之前开始。

调度需要满足所有约束条件。

为了记录约束条件，我们构建一个图$G$，其顶点为作业：$x_1, x_2, \ldots, x_n$。如果$x_i$和$x_j$不能在同一天完成，则用一条无向边连接它们。如果$x_i$需要在$x_j$开始之前完成，则用一条从$x_i$指向$x_j$的有向边连接它们。

如果图$G$很复杂，调度问题会非常困难。现在我们假设问题的约束条件并不复杂：需要处理的图$G$总是一棵树（忽略边的方向后）。你的任务是找出此类输入的最优调度所需的天数。你可以使用以下结论：

如果$G$是一棵树，则所需的天数为$k$或$k+1$，其中$k$是$G$中包含的最大有向路径的顶点数，即路径$P = (x_1, x_2, \ldots, x_k)$，其中对于每个$i = 1, 2, \ldots, k-1$，存在一条从$x_i$指向$x_{i+1}$的有向边。

图1是这样一个例子。有六个作业：1, 2, 3, 4, 5, 6。从图中可知，作业1和作业2必须在不同的日期完成。作业1需要在作业3之前完成，作业3在作业5之前，作业2在作业4之前，作业4在作业6之前。可以验证，完成所有作业的最少天数为4天。在此例中，包含最多顶点的有向路径的顶点数$k$为3。

输入
输入由若干棵树（边可能是有向或无向的）组成，记为$T_1, T_2, \ldots, T_m$，其中$m \leq 20$。每棵树最多有200个顶点。我们将每棵树表示为有根树（仅为方便表示，根是任意选择的顶点）。每棵树的信息包含在若干行中。每行以一个顶点（正整数）开头，后跟其所有子节点（也是正整数），然后以0结尾。注意0不是顶点，表示该行的结束。其中一些边是有向的。边的方向可以从父节点指向子节点，也可以从子节点指向父节点。如果边从父节点指向子节点，则在该子节点后加上字母“d”（表示向下边）。如果边从子节点指向父节点，则在该子节点后加上字母“u”（表示向上边）。如果边是无向的，则不在子节点后加任何字母。

第一个样例输入对应图1的示例。

每行中的连续顶点（数字或带字母的数字）用单个空格分隔。单独一行的0表示该树的结束。下一棵树从下一行开始。连续两行的单个0表示输入结束。

输出
每个测试用例输出一行。每行包含一个数字，表示该测试用例中完成所有作业的最少天数。

输入数据 1

1 2 3d 0  
2 4d 0  
3 5d 0  
4 6d 0  
0  
1 2d 3u 4 0  
0  
1 2d 3 0  
2 4d 5d 10 0  
3 6d 7d 11 0  
6 8d 9 12 0  
0  
1 2 3 4 0  
2 5d 0  
3 6d 0  
4 7d 0  
5 8d 0  
6 9d 0  
7 10d 0  
0  
0  

输出数据 1

4  
3  
4  
3  

来源
Kaohsiung 2006