Labyrinth#7215
Create a program that will help the hero of Jerome K. Jerome's "Three Men in a Boat, to say nothing of the Dog" Harris to quickly get out of the Hampton Court labyrinth. The maze on the plan looks like a rectangle, which sides are directed from west to east or from north to south (as far as possible, considering the spherical shape of the Earth). The dimensions of the labyrinth in yards (English measure of length, approximately cm) along the parallel and the meridian are expressed in positive integers and respectively, and its total area m \cdot n does not exceed (square yards). The entire maze is divided into squares with a side length of yard. Some of the squares are planted with bushes with thorns, that can be only bypassed.
The first line contains two positive integers and - the dimensions of the maze in yards. The following lines of characters each contain a maze scheme, in which the character " " (space) means a free square of the surface, the character "U" means a square with a bush, a cross (addition sign) "+" is a Harris' starting location. The elements of the - st and - th lines and - st and - th columns correspond to the exit from the maze, if they are a space or an addition sign. Movement in the maze is possible in the directions of the cardinal points to an adjacent square free from bushes. Moving north, south, west or east corresponds to movement up, down, left, or right one character on the input diagram.
The first line must contain the smallest number of steps of length yard that Harris must take to get out of the maze.
The second line should contain a description of such a shortest path - steps from the first to the last, where the letter n denotes a step to the north, s to the south, e to the east, w to the west.
If Harris is already at the exit, then the first line must contain only the number , and the second line must be empty.
If it is impossible to get out of the maze (we will not discuss how in this case Harris got to the corresponding place in the maze), then the only line should contain only the number .
Example 1