590. Determine the size of the largest square submatrix consisting of only 1's in a binary matrix

0

Medium

Given a binary matrix with dimensions `M × N`, determine the size of the largest square submatrix consisting of only `1's`.

For example, in the following matrix:

0 0 1 0 1 1
0 1 1 1 0 0
0 0 1 1 1 1
1 1 0 1 1 1
1 1 1 1 1 1
1 1 0 1 1 1
1 0 1 1 1 1
1 1 1 0 1 1
The largest square submatrix of `1's` has a size of `3`.

Input Format

The input consists of two integers, M and N, representing the number of rows and columns of a binary matrix.
This is followed by M*N integers representing the elements of the binary matrix.

Output Format

The output is an integer representing the size of the largest square submatrix consisting of only `1's` and with a size of 1.

Example

Input

10 10 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1

Output

2

Constraints

0<=M,N<=50
0<=mat[i][j]<=1