PROGRAMMING:Operation Libya (Ningbo primary school, 2011)
Since March 16, 2011, the riots in Libya have been escalating, which has seriously endangered the safety of ordinary people and personnel working in Libya. In order to rescue the compatriots in Libya as soon as possible, according to the situation in Libya, the Chinese government tells every citizen in Libya how to act to get to a safe place as soon as possible, and then the plane, ship and car sent by our country will pick them up.
Suppose the map of Libya can be described as a rectangle with n rows and m columns, the compatriot a to be rescued is in one row and one column, and the safe target is in n rows and m columns. Small a can only move to the adjacent up, down, left and right directions each time, that is, if the current position of small a is I row J column, the next position of small a will reach one of the four positions I-1 row J column, I + 1 row J column, I row J-1 column and I row j + 1 column. Of course, small a cannot move out of the rectangle of n row m column.
Libya is a country with many deserts and complex terrain. Some places are very dangerous and people can't go there.
Given the map of Libya, please tell little a how fast it takes to walk from the starting point (1,1) to the end point (n, m)?
###Input format:
The first line has two positive integers n, m (1 ≤ n ≤ 2000, 1 ≤ m ≤ 2000), which are separated by a space, indicating that the terrain of Libya can be divided into n rows and m columns.
Next, N lines, M characters in each line, respectively represent the information of the location in the map. Among them:
The character "*" indicates that this position is a position that cannot be reached by buildings, rivers, mines, etc. (ensure that the starting and ending points are not "*");
The decimal point "." means that people can go to this position.
###Output format:
There is only one row, which has only one positive integer. How many steps does a need from the beginning to the end.
###Input example:
```in
3 5
.*...
...*.
*..*.
```
###Output example:
```out
eight
```
answer：If there is no answer, please comment
Suppose the map of Libya can be described as a rectangle with n rows and m columns, the compatriot a to be rescued is in one row and one column, and the safe target is in n rows and m columns. Small a can only move to the adjacent up, down, left and right directions each time, that is, if the current position of small a is I row J column, the next position of small a will reach one of the four positions I-1 row J column, I + 1 row J column, I row J-1 column and I row j + 1 column. Of course, small a cannot move out of the rectangle of n row m column.
Libya is a country with many deserts and complex terrain. Some places are very dangerous and people can't go there.
Given the map of Libya, please tell little a how fast it takes to walk from the starting point (1,1) to the end point (n, m)?
###Input format:
The first line has two positive integers n, m (1 ≤ n ≤ 2000, 1 ≤ m ≤ 2000), which are separated by a space, indicating that the terrain of Libya can be divided into n rows and m columns.
Next, N lines, M characters in each line, respectively represent the information of the location in the map. Among them:
The character "*" indicates that this position is a position that cannot be reached by buildings, rivers, mines, etc. (ensure that the starting and ending points are not "*");
The decimal point "." means that people can go to this position.
###Output format:
There is only one row, which has only one positive integer. How many steps does a need from the beginning to the end.
###Input example:
```in
3 5
.*...
...*.
*..*.
```
###Output example:
```out
eight
```
answer：If there is no answer, please comment