Largest Square

Time limit5sMemory limit256 MB

Summary

Given a 0/1 matrix, find the side length of the largest all-ones square submatrix.

Level: Medium5 of 10
Topics: Dynamic programming, Matrix
Solved: No attempts yet

Problem

Given an $N \times M$ matrix made up of $0$ s and $1$ s, write a program that finds the largest square submatrix consisting entirely of $1$ s.

Input

The input consists of several test cases. The first line of each test case contains $N$ and $M$ ( $1 \le N, M \le 1{,}000$ ). Each of the next $N$ lines contains $M$ numbers separated by spaces. The input ends with a line containing two zeros.

Output

For each test case, output the side length (width or height) of the largest square. If no such square exists, output $0$ .

Examples1

Example 1

Input

4 5
0 1 0 1 1
1 1 1 1 1
0 1 1 1 0
1 1 1 1 1
3 4
1 1 1 1
1 1 1 1
1 1 1 1
6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0

Expected output

3
3
0