题目描述

基洛夫在做一个游戏。这个游戏是这样的：

一开始，矩阵左上角会发出一道光束，且一开始的方向是朝右的。基洛夫可以在一些格子摆放镜子，合理调整镜子的角度可以使得光束的方向发生变化。

基洛夫希望用尽可能少的镜子使得发射出来的光束可以到达右下角，且光束需要朝右离开矩阵。

输入格式

第一行为两个数 $n,m$，为矩阵行列数。

往后 $n$ 行为矩阵内容，其中 # 代表可以摆放镜子的地方，. 表示不能摆放镜子的地方。

输出格式

一个数，为最后需要留下来的镜子的最少个数。

如果无论如何光束也无法满足题目要求，输出 $-1$。

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

2

提示

对于样例，选择在 $(1,2)(4,2)$ 两处摆放镜子即可。

数据规模与约定

对于 $100\%$ 的数据，保证 $1\leq n,m\leq 1000$。