题目描述Description

There is a rooted tree, some edges are undirected, while others are directed. We want to change maximum number of undirected edges to directed edges, but we don’t want the length of the longest directed chain to be increased. Note that undirected edges are not allowed in a directed chain. For example, if we have a “linear graph” 1->2->3-4, we cannot change 3-4 into 3->4 because the previous longest directed chain (1->2->3) would be extended to 1->2->3->4. However, we can change 3-4 into 3<-4 without extending the longest chain.

输入格式Input

There will be at most 1200 test cases. Each test case contains several lines. In each line, the first integer u is the node that is described, followed by its sons, terminated by a zero. The direction of an edge can be from father to son, and can also be from son to father. If the edge is from father to son, then we put a letter “d” after that son (meaning that it is a downward edge). If the edge is from son to father, then we put a letter “u” after that son (meaning that it is an upward edge). If the edge is undirected then we do not put any letter after the son. Nodes are numbered 1 to n (2<=n<=300) from top to down, left to right (so the first line is always root). Leaves are not given in the input. The test case ends with u=0. Most test cases have very few nodes.

输出格式Output

For each test case, print the case number, the number of changed edges, followed by the changed edges with directions. Each directed edge is formatted as (i,c), which means the i-th undirected edge is changed to direction c. The undirected edges are numbered from 1, in the same order they appear in the input.

If there are several optimal solutions, print the lexicographically smallest one. When comparing two changes (i1,c1) and (i2,c2) lexicographically, we first compare i1 and i2, if i1 and i2 are equal, we compare c1 and c2. For example (2,u) < (11,d), and (3,d) < (3,u).

样例Sample

出题Author

SRbGa

来源Source