The Running Man

A man has escaped from prison. To avoid the police, he runs into a square maze made of paths, doors, and walls. Each door connects two or more paths. The maze has exactly one entrance, located on its border, which is also its only exit.

Using a remote control, the police can lock any single door inside the maze except the entrance; a locked door becomes impassable, just like a wall. Initially every door is unlocked. The running man's current cell is known and is always a path cell. He moves one cell at a time in the four cardinal directions (up, down, left, right); diagonal moves are not allowed. He can never stand on a wall or on a locked door. He escapes if and only if he can reach the entrance cell.

Help the police trap the man in the maze forever by locking exactly one door (different from the entrance). Decide whether this is possible, and if so, report every door whose locking alone prevents the man from escaping. The maze is at most $50 \times 50$ cells.

The input is read from standard input.

• The first line contains one positive integer $N$ ($1 \le N \le 50$), the side length of the maze in cells.
• The second line contains two integers giving the running man's position, separated by a space. Coordinates are 1-based and start from the lower-left corner $(1, 1)$; the first number is the horizontal coordinate (left to right) and the second is the vertical coordinate (bottom to top).
• Each of the next $N$ lines describes one row of the maze, from the top row down to the bottom row, with the $N$ cell symbols separated by single spaces. The symbols are: D a door, E the entrance/exit, P a path, and W a wall that no one can pass through.

The running man always stands on a P cell, and there is exactly one E cell on the border.

Print the following to standard output.

• The first line is YES if the man can be trapped by locking a single door, or NO otherwise.
• If the answer is YES, the second line contains one integer: the number of qualifying doors (doors whose locking alone stops the man from reaching the entrance).
• Then print those doors, one per line, each as its horizontal and vertical coordinates separated by a space. Sort the doors by ascending horizontal coordinate, breaking ties by ascending vertical coordinate.