D. Цикл
ограничение по времени на тест
3 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Маленький Петя очень любит прямоугольные таблицы, состоящие из символов «0» и «1». Недавно он получил в подарок от мамы одну такую таблицу с n строками и m столбцами. Строки нумеруются сверху вниз от 1 до n, столбцы нумеруются слева направо от 1 до m. Петя сразу же решил во что бы то ни стало найти в таблице самый длинный крутой цикл.

Циклом называется последовательность попарно различных клеток, в которой каждые две последовательно идущие клетки имеют общую сторону, а также первая клетка имеет общую сторону с последней. Цикл называется крутым, если для него одновременно выполняются все следующие условия:

  • Цикл целиком состоит из клеток, содержащих «1».
  • Каждая клетка, принадлежащая циклу, имеет общую сторону ровно с двумя другими клетками, принадлежащими этому циклу.
  • Каждая клетка таблицы, содержащая «1» либо принадлежит циклу, либо находятся снаружи него (см. определение ниже).

Для формального определения понятия «снаружи», нарисуем цикл на плоскости. Каждой клетке цикла (i, j) (i — номер строки, j — номер столбца) поставим в соответствие точку на плоскости с координатами (i, j). Соединим отрезком прямой каждую пару точек, для которых соответствующие им клетки принадлежат циклу и имеют общую сторону. Таким образом, на плоскости мы получим замкнутую ломаную без самопересечений и самокасаний. Эта ломаная делит плоскость на две связные области: конечной и бесконечной площади. Считается, что клетка (r, c) лежит снаружи цикла, если она не принадлежит циклу и соответствующая ей точка на плоскости с координатами (r, c) лежит в области бесконечной площади.

Помогите Пете найти длину самого длинного крутого цикла в таблице. Длиной цикла называется количество клеток, принадлежащих ему.

Входные данные

Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 1000) — количество строк и столбцов в таблице, соответственно. Каждая из следующих n строк содержит по m символов. Каждый символ может быть либо «0», либо «1».

Выходные данные

Выведите одно число — длину самого длинного крутого цикла в таблице. Если таких циклов не существует, выведите 0.

Примеры
Входные данные
3 3
111
101
111
Выходные данные
8
Входные данные
5 5
01010
10101
01010
10101
01010
Выходные данные
0
Входные данные
7 7
1111111
1000101
1000101
1000101
1000111
1000001
1111111
Выходные данные
24
Входные данные
5 5
11111
10001
10101
10001
11111
Выходные данные
0
Примечание

В первом примере есть всего один цикл, он же является крутым.

Во втором примере вообще не существует ни одного цикла.

В третьем примере есть два крутых цикла: один длины 12, другой длины 24.

В четвертом примере также есть всего один цикл, но он не является крутым, поскольку существует клетка, содержащая «1», которая находится внутри этого цикла.