Largest 1-Square Submatrix

You are given an N x N matrix of 0s and 1s. Your task is to find the size (i.e., the side length) of the largest square submatrix that consists entirely of 1s.

The algorithm is based on the following recurrence relation in dynamic programming:

\(dp_{i,j} = \min\{dp_{i-1,j},\; dp_{i,j-1},\; dp_{i-1,j-1}\} + 1\) if \(matrix[i][j] = 1\) and \(dp_{i,j} = 0\) if \(matrix[i][j] = 0\).

If the matrix is empty, the result should be 0.

inputFormat

The first line contains an integer N, representing the dimension of the square matrix. The following N lines each contain N space-separated integers (0 or 1) representing the matrix.

outputFormat

Output a single integer: the side length of the largest square submatrix that contains only 1s.## sample

5
0 1 1 0 1
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
0 1 1 0 1

3