beecrowd | 1473

Lines of Containers

Maratona de Programação da SBC Brasil
Timelimit: 1

A shipment of Nlogs, the main export product from Nlogonia, is in the harbour, in containers, ready to be shipped. All containers have the same dimensions and all of them are cubes. Containers are organized in the cargo terminal in L lines and C columns, for a total of LC containers. Each container is marked with a distinct identification number, from 1 to LC.

Each one of the L container lines will be loaded in a different ship. To make it simpler when unloading at each destination country, containers from a line must be organized such that the identifiers are in sequential order. More precisely, the first line must have the containers identified from 1 to C in increasing order, line 2 must have containers numbered from C +1 to 2C (in increasing order), and so on until the last line. which will have containers numbered (L−1)C +1 to LC (again, in increasing order). Figure (a) shows the organization of a shipment with 5 lines and 4 columns of containers.

A crane is able to move either a full line or a full column of containers. It cannot move other groupments or individual containers.

In night before the loading, a group of workers operated the cranes to swap shipment lines and columns as a way of protest because of low salaries. Figure (b) shows the configuration after swapping lines 1 and 4; Figure (c) shows the configuration after another swap, this time between colummns 2 and 3.

The loading must be done today, but before starting the containers must be reorganized as described previously. You must write a program which, given the information about the position of every container after the protest, determines whether you can reposition the containers in such way  that every one of them is in its expected positions, using only cranes. If repositioning is possible, you must also calculate the smallest number of column and line swaps needed to do it.


The input contains several test cases and ends with EOF. The first line of of a test case contains two integers L and N (1 ≤ L, N ≤ 300) which describe, respectively, the number of lines and columns of the shipment. The next L lines show the configuration of the containers after the workers protest. Each of these L lines will have C integers Xl,c (1 ≤ Xl,cLC), indicating the position of a container. Every integer between 1 and LC appears exactly once in the input.


For each test case your program must produce a single line, containing a single integer, the minimum number of column and line swaps needed to place the containers in their original positions. If there is no way to place the containers in their original positions using only cranes, the line must contain only the character ‘*’.

Sample Input Sample Output

2 2
3 4
1 2
3 3
9 2 4
5 8 7
6 1 3
5 4
13 15 14 16
5 7 6 8
9 11 10 12
1 3 2 4
17 19 18 20