Given an N x M matrix of all 1s and 0s, find the largest submatrix which is a square containing all 1s.

Input 

There will be several test cases in the input. Each test case will begin with two integers, N and M (1N, M1, 000) indicating the number of rows and columns of the matrix. The next N lines will each contain M space-separated integers, guaranteed to be either 0 or 1. The input will end with a line with two 0s.

Output 

For each test case, print a single integer, indicating the width (and height) of the largest square of all 1s, or 0 if there are no 1s. Print no extra spaces, and do not print any blank lines between answers.

Sample 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

Sample Output 

3 
3 
0

#include <stdio.h>
#include <string.h>
#define min(x, y) ((x) < (y) ? (x) : (y))
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int n, m;
    int i, j, A[1001], B[1001];
    while(scanf("%d %d", &n, &m) == 2) {
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        if(n == 0 && m == 0)
            break;
        int *ta = A, *tb = B, *tc;
        int ans = 0, x, t;
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= m; j++) {
                ReadInt(&x);
                if(x) {
                    ta[j] = ta[j-1];
                    ta[j] = min(ta[j], tb[j-1]);
                    ta[j] = min(ta[j], tb[j]);
                    ta[j]++;
                    if(ta[j] > ans)
                        ans = ta[j];
                } else
                    ta[j] = 0;
            }
            tc = ta, ta = tb, tb = tc;
        }
        printf("%d\n", ans);
    }
    return 0;
}