CF1214D.Treasure Island

All of us love treasures, right? That's why young Vasya is heading for a Treasure Island.

Treasure Island may be represented as a rectangular table $n \times m$ which is surrounded by the ocean. Let us number rows of the field with consecutive integers from $1$ to $n$ from top to bottom and columns with consecutive integers from $1$ to $m$ from left to right. Denote the cell in $r$-th row and $c$-th column as $(r, c)$. Some of the island cells contain impassable forests, and some cells are free and passable. Treasure is hidden in cell $(n, m)$.

Vasya got off the ship in cell $(1, 1)$. Now he wants to reach the treasure. He is hurrying up, so he can move only from cell to the cell in next row (downwards) or next column (rightwards), i.e. from cell $(x, y)$ he can move only to cells $(x+1, y)$ and $(x, y+1)$. Of course Vasya can't move through cells with impassable forests.

Evil Witch is aware of Vasya's journey and she is going to prevent him from reaching the treasure. Before Vasya's first move she is able to grow using her evil magic impassable forests in previously free cells. Witch is able to grow a forest in any number of any free cells except cells $(1, 1)$ where Vasya got off his ship and $(n, m)$ where the treasure is hidden.

Help Evil Witch by finding out the minimum number of cells she has to turn into impassable forests so that Vasya is no longer able to reach the treasure.

我们大家都喜欢宝藏，对吧？因此，年轻的瓦夏正前往一座宝藏岛。

宝藏岛可以表示为一个 $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)$（宝藏所在地）之外的任意数量的空旷格子上生长森林。

请帮助这位邪恶女巫，求出她至少需要将多少个格子变为不可通行的森林，才能使得瓦夏再也无法抵达宝藏。

First line of input contains two positive integers $n$, $m$ ($3 \le n \cdot m \le 1\,000\,000$), sizes of the island.

Following $n$ lines contains strings $s_i$ of length $m$ describing the island, $j$-th character of string $s_i$ equals "#" if cell $(i, j)$ contains an impassable forest and "." if the cell is free and passable. Let us remind you that Vasya gets of his ship at the cell $(1, 1)$, i.e. the first cell of the first row, and he wants to reach cell $(n, m)$, i.e. the last cell of the last row.

It's guaranteed, that cells $(1, 1)$ and $(n, m)$ are empty.

输入的第一行包含两个正整数 $n$、$m$（$3 \le n \cdot m \le 1\,000\,000$），表示岛屿的尺寸。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串 $s_i$，用于描述岛屿：字符串 $s_i$ 的第 $j$ 个字符为 “#” 表示单元格 $(i, j)$ 是一片不可通行的森林；为 “.” 则表示该单元格为空地且可通行。需要提醒的是，瓦夏从单元格 $(1, 1)$（即第一行的第一个单元格）下船，并希望到达单元格 $(n, m)$（即最后一行的最后一个单元格）。

保证单元格 $(1, 1)$ 和 $(n, m)$ 均为空地。

Print the only integer $k$, which is the minimum number of cells Evil Witch has to turn into impassable forest in order to prevent Vasya from reaching the treasure.

输出唯一的整数 $k$，即恶毒女巫为阻止瓦西娅到达宝藏所需将最少的格子变为不可通行森林的数量。

The following picture illustrates the island in the third example. Blue arrows show possible paths Vasya may use to go from $(1, 1)$ to $(n, m)$. Red illustrates one possible set of cells for the Witch to turn into impassable forest to make Vasya's trip from $(1, 1)$ to $(n, m)$ impossible.

下图展示了第三个样例中的岛屿。蓝色箭头表示瓦夏从 $(1, 1)$ 到 $(n, m)$ 可能采用的路径；红色部分表示女巫可能将其变为不可通行森林的一组单元格，从而使瓦夏无法从 $(1, 1)$ 到达 $(n, m)$。