Маршрут с одним сносом

В городе кварталы образуют прямоугольную сетку. По некоторым кварталам можно пройти, а некоторые перекрыты стеной.

Ты идёшь из северо‑западного угла (верхняя левая клетка) в юго‑восточный (нижняя правая клетка). За весь путь ты можешь снести стену ровно в одном квартале (или не сносить вообще), и после этого этот квартал становится проходимым.

Переходить можно только между клетками с общей стороной.

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

Формат ввода

В первой строке два числа R и C — число строк и столбцов. Дальше идут R строк по C символов:

• . — свободный квартал,
• # — стена.

Гарантируется, что в первой и последней клетке стоит ..

Формат вывода

Одно целое число — минимальное число шагов, либо -1.

Ограничения

• 1 ≤ R ≤ 1000
• 1 ≤ C ≤ 1000
• R * C ≤ 10^6

Пример

Ввод:

3 4
....
.##.
....

Вывод:

5