D. Dice problem
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Куб, находящийся во владении команды Снежный Куб и являющийся её талисманом, представляет собой кубик единичного размера. Одна его грань окрашена в красный цвет, противоположная ей — в синий, остальные четыре белы как снег. Кубик стоит на своей красной грани в левом верхнем углу доски $$$N \times M$$$. Тимур с Еруланом (только с разрешения Александры, конечно) могут перекатить куб через ребро на одну из четырёх соседних клеток доски, если она не занята. Какое наименьшее количество перекатываний им понадобится, чтобы этот куб оказался на своей начальной позиции, стоя на синей грани?

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

На первой строке два целых числа $$$N$$$ и $$$M$$$ от 1 до 100. В следующих $$$N$$$ строках матрица $$$N$$$ на $$$M$$$ — описание доски: '#' — недоступные клетки, '.' — свободные клетки. Гарантируется, что клетка, на которой изначально находится кубик, свободна.

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

Одно целое число — минимальное количество перекатов. Если такой последовательности перекатов не существует, вывести $$$-1$$$.

Примеры
Входные данные
3 3
.##
...
...
Выходные данные
8
Входные данные
3 3
.##
..#
...
Выходные данные
-1
Примечание

В первом примере подходит следующая последовательность: вниз, вправо, вправо, вниз, влево, влево, вверх, вверх.