题目描述

给定一个 $n \times m$ 的迷宫，. 表示可通行，# 表示墙。小明从左上角 $(1,1)$ 出发，每次可以上下左右走一步，求到达右下角 $(n,m)$ 的最少步数。无法到达输出 $-1$。

输入格式

第一行两个整数 $n, m$。
接下来 $n$ 行，每行 $m$ 个字符，表示迷宫。

输出格式

一个整数，表示最少步数（无法到达输出 $-1$）。

样例

输入

3 3
...
.#.
...

输出

4

数据范围

• 对于 $30\%$ 的数据：$n, m \le 10$；
• 对于 $100\%$ 的数据：$1 \le n, m \le 500$。