Largest Square Submatrix

Given an n × m matrix of integers, your task is to determine the side length of the largest square submatrix in which all elements are identical. A submatrix is defined as a contiguous block of cells in the original matrix.

A dynamic programming approach can be used to solve this problem. For each cell in the matrix (except those on the top row or the leftmost column), we can compute the side length of the largest square submatrix ending at that cell using the recurrence:

\(dp[i][j] = \min(dp[i-1][j],\, dp[i][j-1],\, dp[i-1][j-1]) + 1\)

if the current cell has the same value as its top, left, and top-left neighbors. Otherwise, \(dp[i][j] = 1\) (each cell alone forms a 1×1 square). The maximum value in the dp table represents the side length of the largest homogeneous square submatrix.

For example, given the matrix:

1 1 1 0 0
1 1 1 0 0
1 1 1 1 1
0 0 1 1 1

the largest square submatrix where all elements are identical has side length 3.

inputFormat

The input is read from standard input (stdin) and has the following format:

 n m
 a[0][0] a[0][1] ... a[0][m-1]
 a[1][0] a[1][1] ... a[1][m-1]
 ...
 a[n-1][0] a[n-1][1] ... a[n-1][m-1]

where n is the number of rows and m is the number of columns of the matrix. Each of the next n lines contains m integers representing a row of the matrix.

outputFormat

Output a single integer to standard output (stdout) which is the side length of the largest square submatrix composed of identical elements.

## sample

4 5
1 1 1 0 0
1 1 1 0 0
1 1 1 1 1
0 0 1 1 1

3