Description

Lately, our great KK has become obsessed with movies. But he never goes to the cinema, because he has no money in his pocket, and no one to go with! However, KK is not someone who easily bends to fate. He “borrowed” a computer from his dad and started binge-watching day and night.

Obviously, problems always arise for KK: he is used to using the magical software “Baidu Player.” As everyone knows, this software has a powerful feature: it can download while playing. KK never streams directly; instead, he watches while connected to Wi‑Fi (wow… and he says he’s broke!). Then KK noticed the computer getting laggy. To make sure he can shut down and put the computer back in place promptly when his dad makes a surprise inspection, KK had to become a makeshift computer repairman.

KK checked the registry and discovered that the culprit was a square matrix located in a memory region. He calls such a square matrix a “memory killer,” defined as a square submatrix with side length greater than $1$ that remains unchanged after a $180^\circ$ rotation. For example:

$$\begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, \begin{bmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{bmatrix}$$

Of course, there can be more than one “memory killer” in a memory region. Now KK wants to find the side length of the largest “memory killer” in the matrix.

Input Format

There are $N + 1$ lines. The first line contains two integers $N, M$, indicating the size of the memory matrix $N \times M$. Each of the next lines $2$ to $N + 1$ contains $M$ characters representing the memory matrix.

Output Format

Output a single line: the side length of the largest memory killer. If none exists, output $-1$.

3 6
101010
111001
101001

3

Hint

Constraints:

• For $30\%$ of the testdata, $0 < N, M \le 100$.
• For $60\%$ of the testdata, $0 < N, M \le 200$.
• For $100\%$ of the testdata, $0 < N, M \le 300$.

Translated by ChatGPT 5