After attending the lectures for all his normal courses, Max has to attend his List I Communication credit lecture.
To get to his lecture, he has to traverse through a hallway made of either students represented with an
S or empty spaces represented with a
He starts walking at (the top-left corner) and wants to get to his class at (the bottom-right corner).
Max can move from one cell to another if both cells are empty space and share a corner or edge (i.e., he can move in all directions).
Since all the other students are walking to their List I Communication credit, they do not move, which enrages Max.
Because Max is enraged, he can remove at most students from the hallway.
Can Max travel from to ?
and will always be empty space.
The first line will contain an integer, , the number of columns in the hallway.
The next lines will contain characters that are each either an
., the hallway filled with students or empty space, respectively.
YES if he can travel from to by removing at most students; otherwise, output
Sample Input 1
6 .SS.SS .SS.S.
Sample Output 1
Explanation for Sample 1
Regardless of the students removed, Max cannot travel from to .
Sample Input 2
5 .S.S. .S.S.
Sample Output 2
Explanation for Sample 2
If the students at and are removed, Max can travel from to .
Note that there are multiple valid solutions.