Умова задачі

Модник Бітаро купив новий килим. Килим має форму прямокутника, поділеного на сітку з $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$.