#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 struct Node{

     int x,y;

 }node[*];

 int dist[][][][];

 int dp[<<][];

 int n,m,state,final_state,start;

 char map[][];

 int dir[][]={{-,},{,},{,-},{,}};

 void bfs(Node &node)

 {

     queue<pair<int,int> >que;

     que.push(make_pair(node.x,node.y));

     dist[node.x][node.y][node.x][node.y]=;

     while(!que.empty()){

         int x=que.front().first,y=que.front().second;

         que.pop();

         for(int i=;i<;i++){

             int xx=x+dir[i][],yy=y+dir[i][];

             if(xx>=&&xx<n&&yy>=&&yy<m&&map[xx][yy]!='D'){

                 if(dist[node.x][node.y][xx][yy]==-){

                     dist[node.x][node.y][xx][yy]=dist[node.x][node.y][x][y]+;

                     que.push(make_pair(xx,yy));

                 }

             }

         }

     }

 }

 bool Judge(int Power)

 {

     memset(dp,-,sizeof(dp));

     dp[(<<start)][start]=Power;

     int res=-;

     for(int i=;i<(<<state);i++){

         for(int j=;j<state;j++){

             if((i&(<<j))==)continue;

             if(dp[i][j]<)continue;

             if(((i&final_state)&final_state)==final_state)res=max(res,dp[i][j]);

             for(int k=;k<state;k++){

                 if((i&(<<k))||(j==k))continue;

                 if(dist[node[j].x][node[j].y][node[k].x][node[k].y]<)continue;

                 if(dp[i][j]-dist[node[j].x][node[j].y][node[k].x][node[k].y]<)continue;

                 dp[i|(<<k)][k]=max(dp[i|(<<k)][k],dp[i][j]-dist[node[j].x][node[j].y][node[k].x][node[k].y]);

                 if(map[node[k].x][node[k].y]=='G')dp[i|(<<k)][k]=Power;

             }

         }

     }

     return res>=;

 }

 int main()

 {

     int low,high,mid,ans;

     while(~scanf("%d%d",&n,&m)){

         if(n==&&m==)break;

         state=;

         final_state=;

         for(int i=;i<n;i++){

             scanf("%s",map[i]);

             for(int j=;j<m;j++){

                 if(map[i][j]=='F'){

                     start=state;

                     node[state].x=i,node[state].y=j;

                     final_state|=(<<state);

                     state++;

                 }else if(map[i][j]=='G'){

                     node[state].x=i,node[state++].y=j;

                 }else if(map[i][j]=='Y'){

                     node[state].x=i,node[state].y=j;

                     final_state|=(<<state);

                     state++;

                 }

             }

         }

         memset(dist,-,sizeof(dist));

         for(int i=;i<state;i++){

             bfs(node[i]);

         }

         low=,high=,ans=-;

         while(low<=high){

             mid=(low+high)>>;

             if(Judge(mid)){

                 ans=mid;

                 high=mid-;

             }else

                 low=mid+;

         }

         printf("%d\n",ans);

     }

     return ;

 }