#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;int dx[]={0,0,-1,1};int dy[]={-1,1,0,0};int vis[44][44];int dis[44][44];int Hash[1111];int Map[44][44];char str[44][44];int len;int n,m;int Begin;int state[1000];const int INF=0xfffffff;int dp[1<<17][17];int Fin;int Ma(int a,int b){    return a>b?a:b;}void bfs(int x,int y){    queue<int > q;    q.push(x*m+y);    memset(dis,0,sizeof(dis));    memset(vis,0,sizeof(vis));    vis[x][y]=1;dis[x][y]=0;    while(!q.empty()){        int cur=q.front();q.pop();        int xx= cur/m;int yy=cur%m;        if(~Hash[cur]){            Map[Hash[x*m+y]][Hash[cur]]= Map[Hash[cur]][Hash[x*m+y]]=dis[xx][yy];        }        for(int i=0;i<4;i++){            int x1=xx+dx[i];int y1=yy+dy[i];            if(x1>=0&&x1<n&&y1>=0&&y1<m&&!vis[x1][y1]&&str[x1][y1]!=‘D‘){                vis[x1][y1]=1; dis[x1][y1]=dis[xx][yy]+1;                q.push(x1*m+y1);            }        }    }}// 建图int gao(int mid){    memset(dp,-1,sizeof(dp));    dp[1<<Begin][Begin] = mid;    int gg=(1<<len);    for(int i=0;i<gg;i++){        for(int j=0;j<len;j++){            if(dp[i][j]==-1) continue;            if((i&(1<<j))==0) continue;            if((i&Fin)==Fin){                return 1;            }            for(int k=0;k<len;k++){                if((i&(1<<k))) continue;                if(Map[j][k]==-1||dp[i][j]<Map[j][k]) continue;                dp[i|(1<<k)][k]=Ma(dp[i|(1<<k)][k],dp[i][j]-Map[j][k]);                if(state[k]) dp[i|(1<<k)][k]=mid;            }        }    }    return 0;} int main(){    while(cin>>n>>m,n||m){        memset(state,0,sizeof(state));        memset(Hash,-1,sizeof(Hash));        memset(Map,-1,sizeof(Map));        Fin = 0;len=0;        for(int i=0;i<n;i++){            scanf("%s",str[i]);            for(int j=0;j<m;j++){                if(str[i][j]==‘S‘||str[i][j]==‘D‘) continue;                Hash[i*m+j]=len;                if(str[i][j]==‘F‘) Begin= len,Fin|=(1<<len);                if(str[i][j]==‘G‘) state[len]=1;                if(str[i][j]==‘Y‘) Fin|=(1<<len);                len++;            }        }        for(int i=0;i<n;i++){            for(int j=0;j<m;j++)            if(~Hash[i*m+j]){                bfs(i,j);            }        }        int l = 0;int r=n*m+10;int gg=-1;        while(l<=r){            int mid= (l+r)>>1;            if(gao(mid)){                gg=mid;r=mid-1;            }            else l=mid+1;        }        printf("%d\n",gg);    }    return 0;}