CF173B Chamber of Secrets

**“密室再次被打开了。”**——这个消息传遍了霍格沃茨，而一些学生因为看到蛇怪而被石化。虽然邓布利多被迫离开了学校，但哈利正尝试进入密室。而这对伏地魔可不是什么好消息。他不希望任何人进入密室。因为他正在吸取金妮的灵魂。 密室是一个 $n×m$ 的矩形网格，其中一些单元格有柱子。光线（蛇怪的凝视）可以穿过柱子而不改变方向。但是通过一些魔咒，我们可以让柱子在接收光线时反射所有光线向四个方向射去。如下图所示。  左边光线穿过没有施魔法的柱子，右边光线穿过施魔法的柱子，效果如图。蛇怪在密室的右下角，向左边凝视。据传说，直接看见蛇怪的眼睛就会马上死亡，而看到通过柱子的反射光线就会被石化。我们知道，密室的入口在左上角，而进入的人必须注视他所要移动的方向。图片就是第一个样例。  给定密室的大小，和普通柱子的位置，伏地魔想要让你对最少的柱子施法，**使所有人不能进入密室**；或者表示不能完成保护密室的任务。

输入的第一行包含两个整数 $n$ 和 $m$ $(2 \le N,M \le 1000)$接下来 $n$ 行每行包含 $m$ 个字符。每个字符都是 `.` 或 `#`。表示密室的一个单元格。如果为 `.`表示为空，如果为 `#` 表示有柱子。

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

图片为样例解释，将两根柱子都施魔法才可以阻止哈利进入密室。