Description

There is a grid on the picture, consisting of $N\times M$ cells. Each cell is colored either black or white. Find a square of maximum area whose interior is black-and-white alternating, that is, any two adjacent unit cells (sharing an edge) must not have the same color.

Input Format

The first line contains two integers $N$ and $M$, denoting the number of rows and columns, respectively. Then follow $N$ lines, each containing $M$ numbers. Each number is $0$ or $1$, indicating that the cell is black or white, respectively.

Output Format

Output a single line containing the side length of the largest square that satisfies the condition.

3 3
0 1 0
1 0 0
1 1 1

2

Hint

Sample Explanation: The square from $(1,1)$ to $(2,2)$ satisfies the condition, and its side length is $2$.

Constraints:

• For $30\%$ of the testdata, $N \le 20$.
• For $60\%$ of the testdata, $N \le 300$.
• For $100\%$ of the testdata, $N \le 1500$.

Translated by ChatGPT 5