Guest 2019 is lost and can't find the park exit. – came the message in Viktor's favorite computer game, RollerCoaster Tycoon. Generations enjoyed the 20-year-old theme park simulator game, which was designed by Chris Sawyer in 1999. Despite of this, it still causes a nightmare when visitors get lost in the complex path system of the park.
A while ago, Viktor found the installer of his favorite game. As a smart programmer, he made up his mind to decompile the game code to source code in C language and started to rewrite the code of Hedge Maze so that it now works in an absurd way. When entering the park, the visitors find themselves at a random point of the maze and have to find the exit field for getting out. With each move, a visitor can take exactly one step onto a field having exactly one common side with the visitor's current field. They can, however, teleport at the edges of the maze: they can move from the rightmost field of a row to the leftmost field of the same row, from the leftmost field of a row to the rightmost field of the same row, from the top field of a column to the bottom field of the same column, and from the bottom field of a column to the top field of the same column. Viktor did not change one thing: visitors cannot move to a field containing a wall.
Mazes are always rectangular. The first line of the input contains two integers separated by
a single space: the first is the number of rows N, and the second is the number of
columns M (2 ≤ N, M ≤ 100).
This is followed by N lines, each containing M characters. An empty field
is denoted by
The program should output one line. If the visitor can reach the exit, and they can do it in
N steps in an optimal way, then output
Sample Input 1
Output for Sample Input 1
Sample Input 2
Output for Sample Input 2
|University of Debrecen; Faculty of Informatics; v. 03/01/2019|