Задача №115302. Побег слайма

Никите на день рождения подарили набор для создания слаймов. Обрадовавшись подарку, Никита сделал квадратного слайма, и положил его на стол. Слайм, испугавшись предстоящих экспериментов Никиты, решил от него сбежать.

Стол представляет собой прямоугольное поле из \(n\) строк и \(m\) столбцов. В некоторых клетках стола находятся дырки, если хотя бы одна клетка слайма окажется на дырке, он упадет со стола. Слайм занимает 4 клетки, и изначально находится в верхнем левом углу поля размером \(2 \times 2\), цель его побега — занять нижний правый угол размером \(2 \times 2\).

Слайм может передвигаться по полю с помощью трансформаций . Трансформация заключается в следующем: одна из клеток слайма передвигается в другую, соседнюю с ней по стороне или углу. После трансформации слайм должен образовывать 4-связную фигуру (иными словами, между любыми двумя клетками слайма должен существовать путь по клеткам слайма, переходящий каждый раз в клетку, соседнюю по стороне).

Слайм хочет сбежать от Никиты как можно быстрее, чтобы его клетки никогда не оказывались на клетках стола с дырками. Найдите минимальное число трансформаций, за которое он сможет это сделать.

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

Первая строка содержит два целых числа \(n\) и \(m\) (\(2 \le n, m \le 3 \cdot 10^5\); \(n \cdot m \le 3 \cdot 10^5\)) — размеры стола.

В следующих \(n\) строках содержатся по \(m\) символов \(a_{i, j}\) — описание стола. Символ « # » обозначает дырку в столе, а символ « . » обозначает поверхность стола.

Гарантируется, что верхний левый и нижний правый углы стола размером \(2 \times 2\) составляют поверхность стола.

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

Выведите минимальное количество трансформаций, в результате которых слайм займет нижний правый угол стола размером \(2 \times 2\), начав в верхнем левом, либо \(-1\), если он не сможет этого сделать.

Примечание

На рисунке приведены трансформации для первого примера. Черным обозначены дырки в столе, серым — клетки слайма. Стрелками обозначены передвижения клеток.

Примеры
Входные данные
3 3
..#
...
#..
Выходные данные
5
Входные данные
3 5
..###
.....
##...
Выходные данные
-1
Сдать: для сдачи задач необходимо войти в систему