U9365.哈利波特与密室（U13-2）

"密室又被打开了"--这个消息传遍了霍格沃茨，一些学生因为看到玄武岩而吓得魂不附体。邓布利多被解雇了，现在哈利又想进入密室。这些对伏地魔来说都不是好消息。问题是，他不想让任何人进入密室。黑魔王正忙着吸金妮的血呢

密室是一个 n × m 长方形网格，其中一些单元格是柱子。光线(和巴斯里斯克的目光)穿过柱子时不会改变方向。但是，我们可以通过咒语让柱子在接收到光线(或目光)时向四个方向反射。如下图所示。

玄武岩位于网格右下方单元格的右侧，并向左看(左下方单元格的方向)。根据传说，任何直视玄武的人都会立即死亡。但是，如果有人通过柱子与玄武的目光相遇，这个人就会被石化。我们知道，通往密室的门位于网格左上角的左侧，任何想要进入密室的人都要从这个位置朝门的移动方向(右上角单元格的方向)看。

鉴于密室的尺寸和规则立柱的位置，伏地魔勋爵要求您找出我们所需的最小立柱数量，以使任何想要进入密室的人都会被石化或直接宣布密室不可能安全。

输入的第一行包含两个整数 n 和 m ($2 \leq n, m \leq 1000$)。接下来的每 n 行包含 m 个字符。每个字符都是 "." 或 "#"，代表密室网格的一个单元格。如果相应单元格为空，则为 "."；如果被柱子占据，则为 "#"。

打印最小立柱数量，如果无法实现，则打印-1

上图显示了第一个示例测试。在第一个示例中，我们应使两列都具有魔法效果。龙图代表玄武，望远镜代表将进入密室的人。黑星表示人将被石化的地方。黄色线条代表玄武的目光在柱子中移动。

CF_173_B