Маленький Петя очень любит прямоугольные таблицы, состоящие из символов «0» и «1». Недавно он получил в подарок от мамы одну такую таблицу с n строками и m столбцами. Строки нумеруются сверху вниз от 1 до n, столбцы нумеруются слева направо от 1 до m. Петя сразу же решил во что бы то ни стало найти в таблице самый длинный крутой цикл.
Циклом называется последовательность попарно различных клеток, в которой каждые две последовательно идущие клетки имеют общую сторону, а также первая клетка имеет общую сторону с последней. Цикл называется крутым, если для него одновременно выполняются все следующие условия:
- Цикл целиком состоит из клеток, содержащих «1».
- Каждая клетка, принадлежащая циклу, имеет общую сторону ровно с двумя другими клетками, принадлежащими этому циклу.
- Каждая клетка таблицы, содержащая «1» либо принадлежит циклу, либо находятся снаружи него (см. определение ниже).
Для формального определения понятия «снаружи», нарисуем цикл на плоскости. Каждой клетке цикла (i, j) (i — номер строки, j — номер столбца) поставим в соответствие точку на плоскости с координатами (i, j). Соединим отрезком прямой каждую пару точек, для которых соответствующие им клетки принадлежат циклу и имеют общую сторону. Таким образом, на плоскости мы получим замкнутую ломаную без самопересечений и самокасаний. Эта ломаная делит плоскость на две связные области: конечной и бесконечной площади. Считается, что клетка (r, c) лежит снаружи цикла, если она не принадлежит циклу и соответствующая ей точка на плоскости с координатами (r, c) лежит в области бесконечной площади.
Помогите Пете найти длину самого длинного крутого цикла в таблице. Длиной цикла называется количество клеток, принадлежащих ему.
Примечание
В первом примере есть всего один цикл, он же является крутым.
Во втором примере вообще не существует ни одного цикла.
В третьем примере есть два крутых цикла: один длины 12, другой длины 24.
В четвертом примере также есть всего один цикл, но он не является крутым, поскольку существует клетка, содержащая «1», которая находится внутри этого цикла.