题目描述

“密室又被打开了”——这条消息传遍了霍格沃茨，一些学生因为看到蛇怪而被吓呆了。邓布利多被解雇了，现在哈利正试图进入密室。这对伏地魔来说不是好消息。问题是，他不想任何人进入会议厅。黑魔王正忙着从金妮身上吸取生命。

《密室》是 $n\times m$ 矩形网格，其中一些单元格是列。一道光线（以及蛇怪的凝视）穿过柱子，但没有改变方向。但是，通过一些咒语，我们可以制作一个柱状魔法，当它接收到光线时，将光线（或凝视）反射到所有四个方向。如下图所示。

蛇怪位于网格右下单元的右侧，朝左看（朝左下单元的方向）。根据传说，任何人如果直接看到蛇怪的目光，就会立即死亡。但是如果有人通过一根柱子看到蛇怪的目光，这个人就会被石化。我们知道通往会议室的门位于网格左上角的左侧，任何想要进入的人都会从该位置朝着它的移动方向（右上单元格的方向）看。

考虑到密室的尺寸和常规立柱的位置，伏地魔要求你找到我们制作魔法所需的最小立柱数量，以便任何想要进入密室的人都会被石化，或者只是宣布密室不可能安全。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$。

接下来 $n$ 行中的每一行都包含 $m$ 个字符。每个字符都是 .或 #，表示腔室网格的一个单元。是 . 如果对应的单元格为空，如果是立柱，则为 # 。

输出格式

输出使柱子变成魔法柱所需的最小数量，如果不可能，则输出 $-1$。

3 3
.#.
...
.#.

2

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

2

样例分析

上图显示了样例 $1$，我们应该使两个列都具有魔力。龙代表蛇怪，双筒望远镜代表进入密室的人。黑星表示人将被石化的地方。黄线代表蛇怪的视线穿过柱子。

数据范围与提示

对于$100 \%$ 的数据：$1 \le n,m \le 1000$ 。