Stacking Bowls

An online retailer sells dinner bowls sourced from many different manufacturers. Each shipment is assembled from several stacks of bowls, one stack per manufacturer. Within each stack the bowls are already sorted by diameter: the smallest bowl is on top and the largest is at the bottom (the diameters are non-decreasing from top to bottom).

To reduce packing time you must combine all of the incoming stacks into a single sorted stack, again with the smallest bowl on top and the largest at the bottom. You may use exactly two kinds of operations:

• Split: divide one stack into two stacks at any point.
• Merge: place one stack directly on top of another. This is allowed only when every bowl of the upper stack is at most as large as every bowl of the lower stack (equivalently, the largest bowl of the upper stack is no larger than the smallest bowl of the lower stack).

If a stack cannot be placed on another in one piece, you must first split it and merge only the compatible part. Given the stacks, determine the minimum number of split and merge operations needed to form one sorted stack.

The input contains one or more test cases and is read until end of file.

Each test case begins with a line containing an integer $n$ ($1 \le n \le 50$), the number of stacks. Each of the next $n$ lines describes one stack: it starts with the stack height $h$ ($1 \le h \le 50$) followed by $h$ integers giving the bowl diameters from the top of the stack to the bottom. Every diameter is an integer no greater than $10000$, and the $h$ diameters are given in non-decreasing order.

For each test case, print a single line Case X: k, where $X$ is the test case number (starting from $1$) and $k$ is the minimum number of split and merge operations needed to combine that test case's stacks into one sorted stack.