给定一棵有根树，其中一些边是有向的，另一些是无向的。我们希望将尽可能多的无向边改为有向边，但要求不能增加最长有向链的长度。注意，无向边不允许出现在有向链中。

例如，如果我们有一个“线性图” $1 \to 2 \to 3-4$，我们不能将 $3-4$ 改为 $3 \to 4$，因为原先的最长有向链（$1 \to 2 \to 3$）会被延长为 $1 \to 2 \to 3 \to 4$。然而，我们可以将 $3-4$ 改为 $3 \gets 4$，而不会延长最长链。

输入格式

最多包含 1200 组测试数据。每组测试数据包含若干行。在每一行中，第一个整数 $u$ 是被描述的节点，后面跟着它的儿子节点，并以 0 结束。边的方向可以是从父亲到儿子，也可以是从儿子到父亲。如果边是从父亲到儿子，我们在该儿子后面加上字母 "d"（表示向下边）。如果边是从儿子到父亲，我们在该儿子后面加上字母 "u"（表示向上边）。如果边是无向的，则不在儿子后面加任何字母。节点编号从 1 到 $n$ ($2 \le n \le 300$)，按从上到下、从左到右的顺序排列（因此第一行总是根节点）。叶子节点不会在输入中给出。测试数据以 $u=0$ 结束。大多数测试数据的节点数很少。

输出格式

对于每组测试数据，输出样例编号，以及被修改的边数，随后列出修改后的边及其方向。每条修改后的边格式为 $(i,c)$，表示第 $i$ 条无向边被修改为方向 $c$。无向边按其在输入中出现的顺序从 1 开始编号。

如果存在多个最优解，请输出字典序最小的一个。在比较两个修改 $(i_1, c_1)$ 和 $(i_2, c_2)$ 的字典序时，首先比较 $i_1$ 和 $i_2$；如果 $i_1$ 和 $i_2$ 相等，则比较 $c_1$ 和 $c_2$。例如 $(2,u) < (11,d)$，且 $(3,d) < (3,u)$。

样例

输入 1

1 2d 3 0
3 4 5 0
0
1 2d 0
2 3d 0
3 4 0
0
1 2d 0
2 3 0
3 4u 0
0
1 2u 3 0
3 4u 5 0
0

输出 1

Case 1: 3 (1,d) (2,u) (3,u)
Case 2: 1 (1,u)
Case 3: 0
Case 4: 1 (2,u)