Problem C: Escaping zombies

Earth has succumbed to a zombie outbreak and the survivors are struggling to stay alive. Rick, the leader of the survivors, has entered a maze while trying to escape a horde of starving zombies. To avoid being eaten he has to reach the exit of the maze as fast as possible. Also, if possible, he has to try to avoid a special chamber that is full of poisonous gas. The poison will not only make him slower, but also easier to detect by zombies. The objective is to help Rick and determine the fastest path between the entry and the exit points of the maze that, if possible, avoids the poisonous chamber. As a last resource our hero might have to run through the poisonous chamber, which will make him to be twice as slower as his usual speed.

Task

A maze is represented by a rectangular grid composed of square chambers. Each movement from one chamber to an adjoining chamber (at north, south, east, or west) takes one time unit, if Rick has not passed through the poisonous chamber. If Rick passes through the poisonous chamber, he will become twice as slower as his usual speed.

The objective is to help Rick and determine the duration of the safest paths from the entry to the exit point of the maze. A path that avoids the poisonous chamber is safer than a path that passes through the poisonous chamber. Besides, faster paths are safer.

Input

The first line contains two integers separated by a single space:

L is the number of lines in the maze; and
C is the number of columns in the maze.

The following L lines contain the representation of the maze. Each line contains C characters. A dot “.” represents a chamber, a hash mark “#” represents a wall, “S” the start point, “E” the exit point, and “P” the poisonous chamber.

Constraints

•	2 ≤ L ≤ 400		Number of lines
•	2 ≤ C ≤ 400		Number of columns

Output

The output consists of one line with information of the safest paths from the initial to the final chamber. The line has “YES”, if the safest paths avoid the poisonous chamber, and “NO” otherwise, followed by a space and the duration of the safest paths. When it is not possible to reach the maze exit, the output line contains “IMPOSSIBLE” .

Input example 1

6 7
S#...#.
.#.#.#.
.#.#.#.
.#.#.#.
.#.#.#.
...P..E

Output example 1

YES 21

Input example 2

6 7
S#...#.
.#.#.#.
.#.#.#.
.#.#.#.
.#.#.#.
.....PE

Output example 2

NO 12

Input example 3

6 7
S#...#.
.#.#.#.
.#.#.#.
.#.#.#.
.#.#.#.
...P.#E

Output example 3

IMPOSSIBLE