任务安排

现在有 $n$ 个任务需要安排。每个任务都需要一天来完成，但是不同的任务可以在同一天开工。任务和任务之间有两种限制关系：

1. 冲突关系：即两个任务不可以在同一天开工。对于有冲突的任务 $i$ 和 $j$，我们用一条无向边来表示。
2. 需求关系：即一个任务必须在另一个任务完工后才能开工（不可以同时开工）。如果 $i$ 任务必须在 $j$ 任务前完成，我们用一条从 $i$ 到 $j$ 的有向边来表示。

那么 $n$ 个任务之间形成了一个 $n$ 个点的混合图。现在我们简化这个问题：$n$ 个任务之间形成的是一棵混合树（即把边去掉方向后形成一棵树）。

求最少多少天能完成所有任务。

输入格式

若干行，每行描述一个非叶子节点，一行只有 $0$ 表示输入结束。

每一行的第一个数为被描述的节点编号，后接若干个数，每个数表示这个节点的一个孩子。每个孩子后面可能跟着一个字母：

• d 表示该边是父亲指向儿子的有向边；
• u 表示该边是儿子指向父亲的有向边；
• 没有跟字母表示这是一条无向边。

每一行的读入以 $0$ 结束，$0$ 后面不会跟字母。

输出格式

仅一行一个数，表示最少天数。

样例输入

1 2 3d 0
2 4d 0
3 5d 0
4 6d 0
0

样例输出

4

样例解释

一个方案如下：

• 第一天：$1$；
• 第二天：$2$、$3$；
• 第三天：$4$、$5$；
• 第四天：$6$。

数据范围

保证树的节点数 $\le 200$。

来源与许可

本题为「任务安排」，题面与测试数据整理自 BZOJ 1545。

样例 1

输入

1 2 3d 0
2 4d 0
3 5d 0
4 6d 0
0

输出

4