You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

稀树草原中，有一段路。

现在有一个正方体方块走在折线路上，它也只会横向或纵向行走，要求方块不超出路的边沿——因为会有可怕的狮子一把抓住你吃掉。

请求出方块在可以从左上走到右下的前提下，方块的最大棱长。

Format

Input

第一行两个整数 $n,m$，为地图的宽和长。

下面 $n$ 行，每行长度为 $m$ 的 $\tt 01$ 序列，0 表示该格子不是路，1 表示该格子是路。

Output

一行一个整数，即答案。

Samples

5 5
11100
11110
01111
00111
00111

2

10 10
1110000000
1110000000
1111100000
1111100000
0001100000
0001111100
0001111100
0011111100
1111111110
0000000011

1

Limitation

$1\le n,m\le 10^3$，保证每一行恰有一段连续的 $1$。