Master Chief is in a very dangerous situation. He is trapped in a building full of Flood. Cortana analyses the situation and comes up with a very dangerous plan. For the unlucky ones who have never played Halo, Master Chief is the good guy, Cortana is the good AI with Master Chief and Flood is a type of parasitic organism (which is bad, obviously).

Cortana scans the building. Her scan reveals that there is a large reservoir of water in the building. Her plan is that she hacks the building’s control system and opens the reservoir’s door so that the building fills up with water, and kills the Flood. But this plan requires that Master Chief escape the building before the entrance is blocked (his suit can't protect him from drowning). The entrance gets blocked when the water reaches it.

The building includes only a single floor. There are many obstacles such as walls, heavy machinery, closed doors, etc. Master Chief cannot go through or jump over them. These obstacles are denoted by a ‘ #‘. Also there is exactly one exit out of this building, denoted by ‘E’, the reservoir door is denoted by ‘R’ and the Master Chief’s initial position is denoted by ‘M’. Given a map of the building, your job is to help Cortana find if Master Chief will be able to get out of the building before the entrance is blocked. It is guaranteed that there is path for water from the reservoir door to the exit, but there may or may not be a path for Master Chief to the exit.

Assume that in one second Master Chief can move one step in one of the four directions, up, down, left or right. In case of water, the water fills up all adjacent directions in one second (i.e. up, down, left and right, and NOT the diagonal directions). For clarity, if we have,

  - - -
 - W -
 - - -

in the next second it will be

- W -
 W W W
 - W -

( ‘W’ stands for water)

But they cannot move to a location if there’s an obstacle there. Also, they cannot move out of the given map.

INPUT:

The first line has two integers P ( the number of rows in the matrix) and Q (the number of columns in the matrix). The next line contains a P X Q matrix, that can have only ‘E’, ’R’, ’-‘, ’M’, or ‘#’ in it. There are no blank spaces in the input.

OUTPUT:

Output a single line containing either, ‘NEGATIVE’ if Master Chief won’t be able to get out, or ‘YES’ followed by the number of seconds he got out before the entrance is blocked.

NOTE: The number of seconds Master Chief gets out before the entrance is blocked may also be 0. ( A close call for Master Chief :) )

CONSTRAINTS:

2<=P,Q<=30