시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 0 0 0.000%

문제

Um carregamento de Nlogs, principal produto de exportaçãao de Nlogônia, está no porto, em contêineres, pronto para ser embarcado. Todos os contêineres têm as mesmas dimensões e são cubos. Os contêineres estão organizados no pátio do porto em L linhas e C colunas, num total de LC contêineres. Cada contêiner está marcado com um número de identificação distinto, de 1 a LC.


Cada uma das L Linhas de Contêiners será embarcada em um navio distinto. Para facilitar o desembarque nos divesos países em que serão entregues, os containeres de uma linha devem estar organizados de forma que os números de identificação estejam ordenados. Mais precisamente, a linha 1 foi organizada no pátio de forma a conter os contêineres identificados de 1 a C ordenados crescentemente, a linha 2 de forma a conter os contêineres de C + 1 a 2C (ordenados crescentemente), e assim por diante, até a linha L, organizada de forma a conter os contêineres de (L − 1)C + 1 a LC (ordenados crescentemente). A figura (a) abaixo mostra a organização de um carregamento com 5 linhas e 4 colunas de contêineres.

O guindaste de embarque é capaz de movimentar ou uma linha completa ou uma coluna completa de contêineres, não sendo capaz de movimentar outros tipos de agrupamentos ou contêineres individuais.

Na noite anterior ao embarque, um grupo de estivadores operou os guindastes para trocar linhas e colunas do carregamento, como forma de protestar quanto aos baixos salários. A figura (b) acima mostra a configuração dos contêineres após a troca das linhas 1 e 4; a figura (c)mostra a configuração após mais uma troca, entre as colunas 2 e 3.

O carregamento precisa ser embarcado ainda hoje, mas antes disso é necessário que os contêineres sejam reorganizados da forma descrita. Você deve escrever um programa que, dada a informação sobre a posição de cada contêiner após o protesto, determine se é possível recolocar os contêineres na forma originalmente prevista utilizando apenas os guindastes, e nesse caso calcular o menor número de trocas de linhas e colunas necessário para esse fim.

입력

A entrada contém vários casos de teste. A primeira linha de cada caso de teste contém dois inteiros L e N (1 ≤ L, N ≤ 300) indicando respectivamente o número de linhas e o número de colunas do carregamento. As L linhas seguintes descrevem a posição dos contêineres depois do protesto dos estivadores. Cada uma dessas L linhas contém C números inteiros Xl,c (1 ≤ Xl,c ≤ LC) indicando a posição de um contêiner. Cada número inteiro entre 1 e LC aparece na entrada, em alguma das L linhas. É garantido que cada número na configuração apareça uma única vez cada e que todos os números entre 1 e LC aparecerão na mesma. O final da entrada é determinado por EOF (fim de arquivo).

출력


Seu programa deve produzir uma única linha para cada caso de teste, contendo um único inteiro, o número mínimo de trocas de linhas e colunas que devem ser realizadas pelo guindaste para recolocar os contêineres na posição original. Se não for possível colocar os contêineres na posção original, utilizando apenas trocas de linhas e colunas, imprima o caractere ‘*’.

예제 입력

2 2
3 4
1 2

예제 출력

1

예제 입력 2

3 3
9 2 4
5 8 7
6 1 3

예제 출력 2

*

예제 입력 3

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

예제 출력 3

2

힌트