Pac-Man

Time limit1sMemory limit256 MB

Summary

Merge two Pac-Men that move in lockstep on a wrapping maze with walls and ghosts using the fewest joystick pushes.

Level: Medium7 of 10
Topics: BFS, Graph, Shortest path
Solved: No attempts yet

Problem

Chungho was playing Pac-Man when one Pac-Man split into two. The two Pac-Men stand on different cells, but they answer the single joystick in the same way. Push north and both move one cell north. Push east and both move one cell east.

The maze is an $M \times N$ grid. A Pac-Man whose destination cell holds a wall stays where it is. A Pac-Man that meets a ghost is eaten on the spot, so a direction is never used when it would send either of the two Pac-Men into a cell holding a ghost. The ghosts never move. A Pac-Man that leaves the maze on one side reappears on the opposite side.

The two Pac-Men do not block each other. They are merged when both stand on the same cell after a move, and passing through each other to swap places is not a merge.

Chungho wants to merge the two Pac-Men as fast as he can. Find the smallest number of moves and the directions he pushes, in order.

Input

The first line has the number of test cases $T$ ( $1 \le T \le 10$ ).

The first line of each test case has the number of rows $M$ and the number of columns $N$ ( $2 \le M, N \le 50$ ). Each of the next $M$ lines has the maze as $N$ characters. The characters mean:

P is a Pac-Man
X is a wall
G is a ghost
. is an empty cell

Every maze holds exactly two P characters, and the two Pac-Men stand on different cells.

Output

Print one line for each test case.

If the two Pac-Men can be merged, print the smallest number of moves, then one space, then the directions in order. North is N, east is E, south is S, and west is W. When several shortest sequences exist, print the one that comes first in lexicographic order, where the letters are ordered E, N, S, W.

If the two Pac-Men cannot be merged, print IMPOSSIBLE.

Examples4

Example 1

Input

3
2 5
.P...
XG.P.
8 8
X...X.X.
X.......
.XXP...X
..X..X..
.PXXXX..
.......X
........
XXXXXXX.
2 2
P.
GP

Expected output

7 WNEENEE
10 EEESSWWWSS
IMPOSSIBLE

Example 2
Input
```
1
2 3
PPX
...
```
Expected output
```
1 E
```
Example 3
Input
```
1
2 6
P..X.P
XXXXXX
```
Expected output
```
2 WW
```

Example 4

Input

4
3 5
X..XP
.....
...PX
3 5
X..XP
...G.
...PX
4 3
PX.
X..
XXP
X.X
4 3
PXG
X..
XXP
X.X

Expected output

3 NEN
6 SEEESE
3 NNE
IMPOSSIBLE