Chamber of Secrets

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

"The Chamber of Secrets has been opened again" — this news has spread all around Hogwarts and some of the students have been petrified due to seeing the basilisk. Dumbledore got fired and now Harry is trying to enter the Chamber of Secrets. These aren't good news for Lord Voldemort. The problem is, he doesn't want anybody to be able to enter the chamber. The Dark Lord is going to be busy sucking life out of Ginny. The Chamber of Secrets is an $ n×m $ rectangular grid in which some of the cells are columns. A light ray (and a basilisk's gaze) passes through the columns without changing its direction. But with some spell we can make a column magic to reflect the light ray (or the gaze) in all four directions when it receives the ray. This is shown in the figure below.  The left light ray passes through a regular column, and the right ray — through the magic column. The basilisk is located at the right side of the lower right cell of the grid and is looking to the left (in the direction of the lower left cell). According to the legend, anyone who meets a basilisk's gaze directly dies immediately. But if someone meets a basilisk's gaze through a column, this person will get petrified. We know that the door to the Chamber is located on the left side of the upper left corner of the grid and anyone who wants to enter will look in the direction of its movement (in the direction of the upper right cell) from that position.  This figure illustrates the first sample test. Given the dimensions of the chamber and the location of regular columns, Lord Voldemort has asked you to find the minimum number of columns that we need to make magic so that anyone who wants to enter the chamber would be petrified or just declare that it's impossible to secure the chamber.

The first line of the input contains two integer numbers $ n $ and $ m $ ( $ 2<=n,m<=1000 $ ). Each of the next $ n $ lines contains $ m $ characters. Each character is either "." or "\#" and represents one cell of the Chamber grid. It's "." if the corresponding cell is empty and "\#" if it's a regular column.

Print the minimum number of columns to make magic or -1 if it's impossible to do.

3 3
.#.
...
.#.

2

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

2

The figure above shows the first sample test. In the first sample we should make both columns magic. The dragon figure represents the basilisk and the binoculars represent the person who will enter the Chamber of secrets. The black star shows the place where the person will be petrified. Yellow lines represent basilisk gaze moving through columns.