## #1052 Maze Problem

86  2 s   128 MB

## Description

Given a maze, find a shortest path from start to goal.

## Input

Input consists serveral test cases.

First line of the input contains number of test case T.

For each test case the first line contains two integers N , M ( 1 <= N, M <= 100 ).

Each of the following N lines contain M characters. Each character means a cell of the map.

Here is the definition for chracter.

Constraint:

• For a character in the map:
• 'S' : start cell
• 'E' : goal cell
• '-' : empty cell
• '#' : obstacle cell
• no two start cell exists.
• no two goal cell exists.

## Output

For each test case print one line containing shortest path. If there exists no path from start to goal, print -1.

### Sample Output

1
5 5
S-###
-----
##---
E#---
---##

9