最大正方形II

题目背景

忙完了学校的事,v 神终于可以做他的“正事”:陪女朋友散步。一天,他和女朋友走着走着,不知不觉就来到了一个千里无烟的地方。v 神正要往回走,如发现了一块牌子,牌子上有有一行小字和一张图,小字说道:“找到图上最大的交错正方形之后和我联系,这块地就是你的了。”在房价疯长的年代,v 神当然不愿错过这个机会,于是开始找了起来……以 v 神的能力当然找不出来了,你能帮 v 神找出来吗?

题目描述

图上有一个矩阵,由 $N\times M$ 个格子组成,这些格子由两种颜色构成,黑色和白色。请找到面积最大的且内部是黑白交错(即两个相连的正方形颜色不能相同)的正方形。

输入输出格式

输入格式


第一行两个整数 $N$ 和 $M$,分别表示行数和列数。接下来有 $N$ 行,每行 $M$ 个数,$0$ 或 $1$ 分别表示这个格子是黑色或白色。

输出格式


仅有一行,表示满足条件最大正方形的边长。

输入输出样例

输入样例 #1

3 3
0 1 0
1 0 0
1 1 1

输出样例 #1

2

说明

### 样例解释 $(1,1)$ 到 $(2,2)$ 这个正方形是满足条件的,它的边长是 $2$。 ### 数据范围及约定 - 对于 $30\%$ 的数据,$N \le 20$; - 对于 $60\%$ 的数据,$N \le 300$; - 对于 $100\%$ 的数据,$N \le 1500$。