题目描述

密室再次被打开了。这个消息传遍了霍格沃茨，而一些学生因为看到蛇怪而被石化。虽然邓布利多被迫离开了学校，但哈利正尝试进入密室。而这对伏地魔可不是什么好消息。他不希望任何人进入密室。因为他正在吸取金妮的灵魂。

密室是一个 $n×m$ 的矩形网格，其中一些单元格有柱子。光线（蛇怪的凝视）可以穿过柱子而不改变方向。但是通过一些魔咒，我们可以让柱子在接收光线时反射所有光线向四个方向射去。如下图所示。

左边光线穿过没有施魔法的柱子，右边光线穿过施魔法的柱子，效果如图。蛇怪在密室的右下角，向左边凝视。据传说，直接看见蛇怪的眼睛就会马上死亡，而看到通过柱子的反射光线就会被石化。我们知道，密室的入口在左上角，而进入的人必须注视他所要移动的方向。图片就是第一个样例。

给定密室的大小，和普通柱子的位置，伏地魔想要让你对最少的柱子施法，使所有人不能进入密室；或者表示不能完成保护密室的任务。

输入格式

第一行包含两个整数 $n$ 和 $m\ (2\le n,m\le 1000)$。

接下来 $n$ 行每行包含 $m$ 个字符。每个字符都是 . 或 #。表示密室的一个单元格。如果为 . 表示为空，如果为 # 表示有柱子。

输出格式

输出所需要施法的柱子在最小值，如果不可能完成，则输出 $-1$。

3 3
.#.
...
.#.

2

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

2