

Chaotic Maze
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 20yearold 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. Input Specification
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 Output Specification
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 