eolymp
Problems

LeChuck’s Revenge

LeChuck’s Revenge

prb88 "I want to be a pirate!" we recall that familiar phrase from Guybrush Threepwood of Monkey Island series. Yes; Guybrush has engaged in another adventure and needs your help seriously, because this time, it’s a matter of life and death. Our Guybrush, in his latest adventure, has sailed to a mysterious island, Udy Island (UI), to find a clue for a more mysterious treasure, but meanwhile LeChuck has informed of this trip and has prepared a trap for Guybrush in UI. UI has a rectangular shape! (as we know this is a mysterious one) and its map can be viewed as a matrix with same element lengths and widths. We call each matrix element a room. Each room can be filled with mountain rocks such that no one can enter it.

For example, imagine the map of island is something like this.

This matrix represents an island map with 6 rows and 7 columns. Rooms with “R” show rock-filled rooms. Guybrush has to start from the room marked by "g" and LeChuck starts by "l". Guybrush has a chance of escaping of this cursed island by reaching the end room which is marked by "e" in the map. In each time unit, Guybrush can move to the rooms adjacent to the current room horizontally or vertically (but not diagonally) if the target room is not a rock-filled room or he can stay in his room. Means he can go one room up, down, left, right or he can stay. In the above example, Guybrush can stay or go one room left at first time unit. All of the above rules apply exactly to LeChuck’s movement too, but with one exception: he can’t enter the end room (room marked with "e"). Means LeChuck can go up, down, left,right one room at a time (as soon as it’s not "R" or "e") or stay, in each time unit. Assume that in each time unit, Guybrush first takes a move (or stays) then LeChuck moves (or stays), in next time unit first one is Guybrush then LeChuck and so on. If Guybrush and LeChuck meet each other in a room, then LeChuck will kill our poor Guybrush immediately. Your task is to find out whether there’s at least one guaranteed path or not. A guaranteed path is a path for Guybrush (from "g" to "e") such that LeChuck can’t catch Guybrush in this path regardless of what he (LeChuck) do in each time unit. For instance, the "Left, Up, Up, Up, Right" sequence (in 5 time units) represents a guaranteed path in the above map, because whatever LeChuck do in this 5 time units, he can’t catch Guybrush.

Input

The first line of input contains a single integer which is the number of test cases. Next there are data lines for test cases. Each test case begins with a line containing two integers, R and C (4 <= R, C <= 30) which are number of rows and columns of island map (UI), respectively. Next there are R lines each contains C characters, representing the map. There are only one "g", "l" and "e" (distinct) marks in the map.

Initially empty, non rock-filled rooms are showed with one space character in input. All rooms located at any borders of map are rock-filled rooms.

Output

There should be one line for each test case in output. If there’s at least one guaranteed path for a test case the word "YES" should be outputted for that test case and "NO" if there’s not. Assume that if there’s a guaranteed path, it should take no longer than 1000 time units for Guybrush to pass through it.

Time limit 1 second
Memory limit 64 MiB
Input example #2
1
6 7
RRRRRRR
R e   R
R     R
R RRR R
R gRl R
RRRRRRR
Output example #2
YES