Cycle

题意翻译

给定一个 $n$ 行 $m$ 列的矩阵，每个元素只可能是 $0$ 或 $1$，希望找出最长的由权值为 $1$ 的位置构成的合法序列。合法序列应当满足以下条件： - 序列中不存在重复的位置。 - 序列中相邻的位置（包括第一个和最后一个之间）应当四联通，即有公共边。 - 序列最后显然会形成一个闭合的环，应当满足**环内**没有权值为 $1$ 的点（看样例应该就能理解了）。

题目描述

Little Petya very much likes rectangular tables that consist of characters "0" and "1". Recently he has received one such table as a gift from his mother. The table contained $ n $ rows and $ m $ columns. The rows are numbered from top to bottom from $ 1 $ to $ n $ , the columns are numbered from the left to the right from $ 1 $ to $ m $ . Petya immediately decided to find the longest cool cycle whatever it takes. A cycle is a sequence of pairwise distinct cells where each two consecutive cells have a common side; besides, the first cell has a common side with the last cell. A cycle is called cool if it fulfills all the following conditions simultaneously: - The cycle entirely consists of the cells that contain "1". - Each cell that belongs to the cycle, has a common side with exactly two other cells that belong to the cycle. - Each cell of the table that contains "1" either belongs to the cycle or is positioned outside of it (see definition below). To define the notion of "outside" formally, let's draw a cycle on a plane. Let each cell of the cycle $ (i,j) $ ( $ i $ is the row number, $ j $ is the column number) correspond to the point $ (i,j) $ on the coordinate plane. Let a straight line segment join each pair of points that correspond to the cells belonging to the cycle and sharing a side. Thus, we will get a closed polyline that has no self-intersections and self-touches. The polyline divides the plane into two connected parts: the part of an infinite area and the part of a finite area. It is considered that cell $ (r,c) $ lies outside of the cycle if it does not belong to the cycle and the corresponding point on the plane with coordinates $ (r,c) $ lies in the part with the infinite area. Help Petya to find the length of the longest cool cycle in the table. The cycle length is defined as the number of cells that belong to the cycle.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1<=n,m<=1000 $ ) — the number of rows and columns in the table, respectively. Each of the following $ n $ lines contains $ m $ characters. Each character can be either "0" or "1".

输出格式

Print a single number — the length of the longest cool cycle in the table. If such cycles do not exist, print 0.

输入输出样例

输入样例 #1

3 3
111
101
111

输出样例 #1

8

输入样例 #2

5 5
01010
10101
01010
10101
01010

输出样例 #2

0

输入样例 #3

7 7
1111111
1000101
1000101
1000101
1000111
1000001
1111111

输出样例 #3

24

输入样例 #4

5 5
11111
10001
10101
10001
11111

输出样例 #4

0

说明

In the first example there's only one cycle and it is cool. In the second sample there's no cycle at all. In the third sample there are two cool cycles: their lengths are 12 and 24. In the fourth sample there also is only one cycle but it isn't cool as there's a cell containing "1" inside this cycle.

题意翻译

给定一个 $n$ 行 $m$ 列的矩阵，每个元素只可能是 $0$ 或 $1$，希望找出最长的由权值为 $1$ 的位置构成的合法序列。合法序列应当满足以下条件： - 序列中不存在重复的位置。 - 序列中相邻的位置（包括第一个和最后一个之间）应当四联通，即有公共边。 - 序列最后显然会形成一个闭合的环，应当满足**环内**没有权值为 $1$ 的点（看样例应该就能理解了）。