Maximum Square

//4867 - Maximum Square

#include <iostream>
#include <cstdio>

using namespace std;

#define forn(i, n) for(int i = 0; i < (int) (n); i++)
#define forsn(i, s, n) for(int i = (s); i < (int) (n); i++)

int r, c;
const int SIZE = 1010;

int M[SIZE][SIZE];
int A[SIZE][SIZE];

int calc(int i1, int j1, int i2, int j2){
    return A[i2][j2]-A[i1][j2]-A[i2][j1]+A[i1][j1];
}

int main(){
#ifdef ACM
    freopen("test.in", "r", stdin);
#endif

    while(scanf("%d %d", &r, &c) && r != 0 && c != 0){
        forn(i, r) forn(j, c) scanf("%d", &M[i][j]);

        forn(i, r+1) A[i][0] = 0; forn(i, c+1) A[0][i] = 0;
        forsn(i, 1, r+1)
            forsn(j, 1, c+1)
                A[i][j] = A[i-1][j] + A[i][j-1] - A[i-1][j-1] + M[i-1][j-1];

        int k = 0;
        forn(i, r) forn(j, c){
            if(M[i][j] == 0) continue;

            int l = 0, u = min(r-i, c-j);
            int a = calc(i, j, i+u, j+u);

            if(a == u*u) k = max(k, u);
            else{
                while(u-l > 1){
                    int m = (l+u)/2;
                    a = calc(i, j, i+m, j+m);

                    if(a == m*m){
                        k = max(k,m); l = m;
                    }else u = m;
                }

                k = max(k, l);
            }
        }

        printf("%d\n", k);
    }

    return 0;
}