Условие задачи

Модник Битаро купил новый ковёр. Ковёр имеет форму прямоугольника, разделённого на сетку из $H$ строк по вертикали и $W$ столбцов по горизонтали, и каждая клетка покрашена в белый или чёрный цвет. Цвет клетки, находящейся в $i$-й строке сверху и $j$-м столбце слева ($1 \le i \le H$, $1 \le j \le W$), является белым, если $j$-й символ строки $S_i$ равен ., и чёрным, если он равен #.

Битаро придумал игру, в которой он ставит фишку на самую верхнюю левую клетку ковра и, выполняя следующую операцию несколько раз, пытается довести фишку до самой нижней правой клетки ковра:

• Выбрать $1$ клетку, которая отличается по цвету от клетки, где сейчас стоит фишка, и является соседней с ней по вертикали или горизонтали, и переместить фишку на эту клетку.

Битаро хочет минимизировать количество операций до достижения цели. Однако в зависимости от узора ковра довести фишку до цели может быть невозможно.

По заданной информации об узоре ковра напишите программу, которая определит, можно ли, повторяя указанную операцию, довести фишку из верхней левой клетки в нижнюю правую клетку, и если возможно, найдёт минимальное количество операций.

Ограничения

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ — строка длины $W$ ($1 \le i \le H$).
• Каждый символ строки $S_i$ равен . или # ($1 \le i \le H$).
• $H, W$ — целые числа.

Подзадачи

1. ($4$ балла) $H = 1$.
2. ($14$ баллов) $H \le 5$, $W \le 5$.
3. ($24$ балла) $H \le 30$, $W \le 30$.
4. ($58$ баллов) Дополнительных ограничений нет.

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

Входные данные подаются из стандартного потока ввода в следующем формате:

H W
S_1
S_2
:
S_H

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

Если путём повторения операции можно довести фишку из верхней левой клетки в нижнюю правую клетку, выведите минимальное количество операций; если это невозможно, выведите -1 в $1$ строке в стандартный поток вывода.

Примеры

Пример ввода 1

4 5
...#.
#####
...#.
#.###

Пример вывода 1

9

Например, можно рассмотреть операции, показанные на рисунке.

В примере слева довести фишку из верхней левой клетки в нижнюю правую можно за $9$ операций, а в примере справа — за $13$ операций.

Поскольку достичь цели менее чем за $9$ операций невозможно, выводим $9$.

Этот пример удовлетворяет ограничениям подзадач $2, 3, 4$.

Пример ввода 2

3 3
...
...
...

Пример вывода 2

-1

Бывают случаи, когда с самого начала нельзя выполнить ни одной операции. В этом случае довести фишку до нижней правой клетки невозможно, поэтому выводим -1.

Этот пример удовлетворяет ограничениям подзадач $2, 3, 4$.

Пример ввода 3

1 5
.#.#.

Пример вывода 3

4

Этот пример удовлетворяет ограничениям всех подзадач.

Пример ввода 4

5 5
###.#
.#...
.#..#
.####
##..#

Пример вывода 4

12

Этот пример удовлетворяет ограничениям подзадач $2, 3, 4$.

Пример ввода 5

7 5
.#.##
##...
.#.##
.###.
##.#.
...#.
##.#.

Пример вывода 5

12

Этот пример удовлетворяет ограничениям подзадач $3, 4$.