Defragmentation

Time limit1sMemory limit128 MB

Summary

Given K files scattered across N disk clusters, find the minimum number of cluster moves to pack them consecutively in file order.

Level: Medium7 of 10
Topics: Graph, Simulation, Union-find
Solved: No attempts yet

Problem

A secure operating system uses a special file system. The whole disk is divided into $N$ clusters of equal size, numbered $1$ to $N$ . Each file occupies one or more clusters, and those clusters may lie anywhere on the disk. Every cluster not occupied by a file is a free cluster. A file is read fastest when all of its clusters lie in consecutive disk clusters in their natural order.

Because the disk rotates at a constant speed, clusters near the beginning of the disk are read faster than clusters near the end. The $K$ files are therefore numbered $1$ to $K$ in order of decreasing access frequency. Let $S_i$ be the number of clusters in file $i$ . In the optimal layout, file $1$ occupies clusters $1, 2, \dots, S_1$ , file $2$ occupies clusters $S_1 + 1, S_1 + 2, \dots, S_1 + S_2$ , and so on.

To reach this layout you perform cluster-moving operations. One cluster-moving operation reads the contents of one occupied cluster into memory and writes them to some free cluster; the source cluster then becomes free and the destination cluster becomes occupied.

Arrange the files into the optimal layout using the minimum possible number of cluster-moving operations.

Input

The input consists of several disk descriptions. The first line of a description contains two integers $N$ and $K$ separated by a space ( $1 \le K < N \le 100000$ ). Then $K$ lines follow; the $i$ -th of them describes file $i$ . It begins with the integer $S_i$ , the number of clusters in file $i$ ( $1 \le S_i \le N - K$ ), followed by $S_i$ integers giving the cluster numbers occupied by that file in their natural order. Each cluster number is between $1$ and $N$ inclusive.

All cluster numbers within one description are distinct, and there is always at least one free cluster. The input ends with a line containing two zeros in place of $N$ and $K$ .

Output

For each disk description, print exactly one line. If at least one move is required, print We need M move operations., where $M$ is the minimum number of cluster-moving operations needed to reach the optimal layout. If the files are already in the optimal layout, print No optimization needed. instead.

Examples3

Example 1

Input

20 3
4 2 3 11 12
1 7
3 18 5 10
30 4
2 1 2
3 3 4 5
2 6 7
8 8 9 10 11 12 13 14 15
0 0

Expected output

We need 9 move operations.
No optimization needed.

Example 2

Input

Expected output

We need 3 move operations.

Example 3

Input

4 1
2 3 4
0 0

Expected output

We need 2 move operations.