Сокровища! Кто не мечтал о них в детстве? Именно так подумал юный Вася и отправился в длительное путешествие к Острову Сокровищ.
Остров Сокровищ представляет собой прямоугольное поле $$$n \times m$$$, окруженное океаном. Пронумеруем строки поля последовательными целыми числами от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы последовательными целыми числами от $$$1$$$ до $$$m$$$ слева направо. Обозначение $$$(r, c)$$$ соответствует клетке, расположенной в строке $$$r$$$ и столбце $$$c$$$. В некоторых клетках острова растут непроходимые леса, а остальные клетки свободные и проходимые. Сокровище закопано в клетке $$$(n, m)$$$.
Вася высадился с корабля в клетку $$$(1, 1)$$$. Теперь он хочет добраться до сокровища. Вася сильно спешит за сокровищем, поэтому может перемещаться только в клетку в следующей строке (вниз) или следующем столбце (вправо), то есть из клетки $$$(x, y)$$$ он может сделать ход только в клетки $$$(x+1, y)$$$ и $$$(x, y+1)$$$. Конечно, Вася не может заходить в клетки, где растёт непроходимый лес.
Злая Ведьма узнала о планах Васи завладеть сокровищами и хочет ему помешать. До начала движения Васи она с помощью своей магии может вырастить непроходимые леса в клетках, которые ранее были свободными. Ведьма может вырастить непроходимый лес в любых клетках, кроме клетки $$$(1, 1)$$$, где уже высадился Вася, и клетки $$$(n, m)$$$, где закопаны сокровища.
Помогите Злой Ведьме определить, на каком минимальном количестве клеток ей придётся вырастить непроходимый лес, чтобы Вася не смог добраться до сокровища?
Первая строка содержит два целых положительных числа $$$n$$$, $$$m$$$ ($$$3 \le n \cdot m \le 1\,000\,000$$$) — размеры острова.
Следующие $$$n$$$ строк содержат строки $$$s_i$$$ длины $$$m$$$, задающие описание острова, $$$j$$$-й символ строки $$$s_i$$$ равен «#», если в клетке $$$(i, j)$$$ острова растёт непроходимый лес и «.», если клетка свободна. Напомним, что Вася высаживается в клетке $$$(1, 1)$$$, то есть в первой клетке первой строки и идёт навстречу сокровищам, находящимся в клетке $$$(n, m)$$$, то есть в последней клетке последней строки.
гарантируется, что клетки $$$(1, 1)$$$ и $$$(n, m)$$$ не содержат леса.
Выведите одно целое число $$$k$$$ — минимальное количестве клеток, в которых Злой Ведьме нужно вырастить непроходимый лес, чтобы Вася не смог добраться до сокровища.
2 2 .. ..
2
4 4 .... #.#. .... .#..
1
3 4 .... .##. ....
2
Следующая картинка изображает осторов в третьем примере. Синим отмечены возможные пути Васи из клетки $$$(1, 1)$$$ в клетку $$$(n, m)$$$, красным отмечены клетки, на которых ведьма может вырастить непроходимый лес, чтобы Вася не смог добраться из $$$(1, 1)$$$ в $$$(n, m)$$$.
