Shortest Path on a Grid

Given a labyrinth represented as a grid of r rows and c columns, you are asked to find the length of the shortest path from the starting cell to the end.
The labyrinth is represented with:
  • The floor is a dot (.).
  • The walls are hashtags (#).
  • The starting point is the capital letter S.
  • The end cell is the capital letter E.
You can move between two adjacent cells (left, right, up, or down) if they’re not walls.
You are asked to find the length of the shortest path between the starting cell and the end cell.

Input

The first line of the input contains two integers r and c (1 ≤ r, c ≤ 1000).
The next r rows contain c columns of characters representing the grid. Each cell is either a floor (.), a wall (#), a starting point (S), or an endpoint (E). It’s guaranteed that there is only a single S and a single E in the whole grid.

Output

The program should print the length of the shortest path from S to E. If there is no path from S to E, the program should print Impossible.

Examples

Input

5 8
########
##.S....
....#.#.
#......#
...#...E
Output

7
 
 
Tip
It’s not always necessary to construct a graph to run a BFS algorithm. Sometimes, you can have implicit graphs like grids and still be able to run a BFS algorithm on them.
Hint
You can treat the grid as your graph and have a two-dimensional array of distances d[][] representing the shortest distance from the starting cell up to the current one.
 

Constraints

Time limit: 15 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in