Note

Python3 got TLE with the intended solution.

Explanation of the Bingo Game

Do you know the bingo game?

Each player is dealt one bingo card of N cells × N cells.
A natural number is written in each cell.

The host puts balls with those numbers written on them into a basket, draws balls at random,
and reads out the numbers written on the drawn balls.
If a number read out by the host is on your card, you erase that cell.
In this game, when a vertical line, a horizontal line, or a diagonal is complete, that is, when N consecutive cells have been erased, you have a "bingo" and receive a prize.

Normally, the host of a bingo game draws balls one at a time, reads them out one at a time, and checks each time whether any participant has a bingo.

* The same natural number never appears more than once on a single card.

Story

There was a lazy bingo game host.
He now wants to determine exactly one winner (the player who gets a bingo first) among the M players.

Because he is lazy, he draws as many balls at once as possible, as long as it can be guaranteed that multiple people will not get a bingo at the same time.
In other words, whereas a normal host draws and reads out numbers one at a time, he draws several balls at once and reads them out all together.
After reading out several balls all together, he has the participants process the group read out together, and checks whether any player has a bingo.

When the possibility of multiple people getting a bingo at the same time cannot be ruled out even if he draws just 1 ball,
he says "If you get a bingo at the same time, settle it with rock-paper-scissors" and then draws just 1 ball.

Now, a bingo game is about to begin. When he draws balls for the very first time, how many balls will he draw?

Problem Statement

You are given information on M bingo cards of N cells × N cells.
Find the maximum integer X such that, when X balls are drawn at once and the number corresponding to each ball is erased,
there is no possibility that the number of cards with a bingo exceeds 1.

Input

N M
C111 C112 ... C11N
C121 C122 ... C12N
...
C1N1 C1N2 ... C1NN
...
CM11 CM12 ... CM1N
CM21 CM22 ... CM2N
...
CMN1 CMN2 ... CMNN

The first line contains N, the size of the bingo cards, and M, the number of players, separated by a single space.
The following N×M lines give the card information for each player, N lines per player.
For example, the N lines starting from line 2 are the card information of player 1, and the next N lines are the card information of player 2.
Each line of the bingo card information contains the natural numbers written in the N cells.

• $ 2 \le N \le 100 $
• $ 2 \le M \le 200 $
• Moreover, $ NM \le 400 $ is satisfied.
• $ 1 \le C_{kij} \le N^2M $
• The same natural number never appears more than once on a single card.

Output

Output the maximum integer X such that, when X balls are drawn at once and the number corresponding to each ball is erased,
there is no possibility that the number of cards with a bingo exceeds 1.
Print a newline at the end.

Sample

2 2
1 2
3 4
5 6
7 8

3

3 2
1 2 3
4 5 6
7 8 9
1 10 3
12 13 14
15 8 6

3

3 4
28 14 15
18 16 25
30 29 4
21 7 2
28 1 10
16 5 12
4 12 10
17 2 5
6 35 18
15 24 9
16 25 29
14 22 10

3