Dot Dot Dot

Time Limit: 2 Seconds

Memory Limit: 65536 KB


Recently DZB is playing a game called Dot Dot Dot. It's a simple game but very interesting. The rule is like this:

The game is played on a N*M grid map, each grid is adjacent with 4 grids(up, down, left, right). There's only one exit on the map, the game finished when the player reach the exit. When the game starts, the player go to the exit step by step. In each step he can only move to adjacent grid. But there's some barriers on the map, each barrier is yellow or green. The player can not go to the grid when there is a barrier or there is outside wall.

The only way to destroy the barriers is to stand on some grid which has a trigger. Each trigger is also yellow or green and can be used only once. When the player stand on it, it will sent shock waves to destroy all the barriers with the same color it could reach directly. Shock waves spread as wide as possible. It can spread on all the connected grids which no barrier is on it, that means if it reach a barrier with different color, it will be blocked too. Notice if the wave can not reach a barrier directly, it can not be destroied, even if it's the same color with the trigger.

Now DZB not only wants to finish the game, but also wants to finish the game with the minimal step, so he ask you for help.


There are multiple test cases. For each test case:

The first line contains two integers N(1≤N≤40), M(1≤M≤40), N is the number of rows of the map, and M is the number of the columns.

The after N lines describe the map, each line has M characters. A character could be:

  • '.' means there's nothing, you can stand there.
  • '*' means the outside wall, we guarantee that the outside wall form a close area and the player is in it.
  • 'Y' means a yellow barrier, you can not stand there unless you have destroied the barrier.
  • 'G' means a green barrier, similar with 'Y'.
  • 'y' means a yellow trigger.
  • 'g' means a green trigger. Notice the number of yellow trigger plus the number of green trigger is no more than 5.
  • 's' means the initial position of the player.
  • 'e' means the exit, the player must go to there finally to finish the game.

There is a blank line between every two cases.

Process to the end of input.


One line for each test case. The minimal step. If can not reach the exit, print -1 instead.

Sample Input

5 17

Sample Output