Largest Identical Square Submatrix

You are given an NxN matrix consisting of integers. Your task is to find the side length of the largest square submatrix (i.e. block) in which all the elements are identical. Formally, you need to determine the maximum integer \(k\) such that there exists some row index \(i\) and column index \(j\) with \(0 \leq i, j \leq N-k\) for which the submatrix:

[ M[i][j],\ M[i][j+1], \dots, M[i][j+k-1] \ M[i+1][j],\ M[i+1][j+1], \dots, M[i+1][j+k-1] \ \vdots \ M[i+k-1][j],\ M[i+k-1][j+1], \dots, M[i+k-1][j+k-1] ]

contains only one unique value.

Input/Output Format

inputFormat

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

N
M[0][0] M[0][1] ... M[0][N-1]
M[1][0] M[1][1] ... M[1][N-1]
...
M[N-1][0] M[N-1][1] ... M[N-1][N-1]

Where N is a positive integer representing the dimensions of the square matrix, and each of the following N lines contains N space-separated integers.

outputFormat

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

4
1 1 1 0
1 1 1 0
1 1 1 0
0 0 0 0

3