URI Online Judge | 1438

Unloading Boxes

By Alessandro de Luna Almeida Brazil
Timelimit: 1

Joãozinho and his family have just moved in. Before the move, he put all of his books in several numbered boxes. To facilitate the removal of the books, he did an inventory, indicating in which box each book was placed and he kept it  in box number 1.

Arriving in his new room, he saw that his parents had kept the boxes in various stacks, arranged in a row, with each stack against the next stack.

Joãozinho is a very systematic boy, so before opening any box, he wants to recover his inventory. Joãozinho is also a very awkward kid. To take a box from a stack, it needs to be at the top of the stack and at least one of its sides, no matter which, has to be free (ie, have no adjacent box).

To do this, Joãozinho needs to unstack some boxes. As his room is quite large, he always has room to put the removed boxes elsewhere, without moving the stacks that his parents set up.

To minimize his effort, Joãozinho wants you to write a program that, given the positions of the boxes in the stacks, determine how many boxes Joãozinho needs to unstack to recover his inventory.


The input consists of several test cases. The first line of each test case contains two integers N and P, indicating, respectively, the number of boxes and the number of stacks (1 ≤ PN ≤ 1000). The boxes are numbered sequentially from 1 to N.

Each of the following lines P describes a stack. Each row contains an integer Qi, indicating how many boxes are in the stack i, followed by a blank space followed by a list of numbers Qi, which are the identifiers of the boxes. The elements of the list are separated by a blank space.

All stacks contains at least one box and all the boxes appear exactly once on the input. The boxes in each stack are listed in order, from the bottom to the top of the stack. All boxes have the same shape.

The end of input is indicated by N = P = 0.

The input must be read from standard input.


For each test case in the input, your program must print a single line, containing a single integer: the minimum number of boxes, besides box 1, that Joãozinho needs to unstack to recover his inventory.

The output should be written on the standard output.

Sample Input Sample Output

4 3
1 3
2 1 2
1 4
4 3
1 3
2 2 1
1 4
0 0