//#define _DEBUG
#include "bits/stdc++.h"
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#ifdef _DEBUG
#define debug(...) CHOOSE((__VA_ARGS__,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
#else
#define debug(...)
#endif
#define rep(index,num) for(int index=0;index<(int)num;index++)
#define rep1(index,num) for(int index=1;index<=(int)num;index++)
#define brep(index,num) for(int index=(int)num-1;index>=0;index--)
#define brep1(index,num) for(int index=(int)num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define puba(a) emplace_back((a))
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
ll INFl=(ll)1e+18+1;
int INF=1e+9+1;
char a[2004][2004];
char moto[2004][2004];
int dismin[2004][2004];
int dp[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int main(){
	int H,W;
	scan(H>>W);
	rep1(i,H){
		scan(a[i]+1);
	}
	rep(i,H+2) a[i][0]=a[i][W+1]='#';
	rep(j,W+2) a[0][j]=a[H+1][j]='#';
	rep(i,H+2) rep(j,W+2) moto[i][j]=a[i][j];
	fill(dismin[0],dismin[2004],INF);
	vpint warp[26];
	pint st,go;
	rep(i,H+2){
		rep(j,W+2){
			if(a[i][j]!='#'){
				if(a[i][j]=='S'){
					st=mp(i,j);
				}
				if(a[i][j]=='G'){
					go=mp(i,j);
				}
				else if('a'<=a[i][j]&&a[i][j]<='z'){
					warp[a[i][j]-'a'].puba(mp(i,j));
				}
				a[i][j]='.';
			}
		}
	}
	pint inizahyo;
	inizahyo=st;
	dismin[st.first][st.second]=0;
	vector<pint> zahyorecord;
	zahyorecord.push_back(inizahyo);
	bool alre[26]={};
	for(int count=1;;count++){
		if(zahyorecord.empty()) break;
		vector<pint> zahyobefore=move(zahyorecord);
		zahyorecord.clear();

		rep(i,zahyobefore.size()){
			rep(j,4){
				pint zahyoto=zahyobefore[i];
				int y=zahyoto.first+dp[j][1];
				int x=zahyoto.second+dp[j][0];
				if(a[y][x]=='.'&&count<dismin[y][x]){
					zahyorecord.puba(mp(y,x));
					dismin[y][x]=count;
				}
			}
			pint zahyoto=zahyobefore[i];
			int y=zahyoto.first,x=zahyoto.second;
			debug(count,y,x);
			if('a'<=moto[y][x]&&moto[y][x]<='z'&&alre[moto[y][x]-'a']==0){
				for(const auto& v:warp[moto[y][x]-'a']){
					if(v==zahyoto) continue;
					int yto=v.first,xto=v.second;
					if(count<dismin[yto][xto]){
						zahyorecord.puba(mp(yto,xto));
						dismin[yto][xto]=count;
					}
				}
				alre[moto[y][x]-'a']=1;
			}

		}
	}
	if(dismin[go.first][go.second]>=INF) prin(-1);
	else prin(dismin[go.first][go.second]);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define rep(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
using ll = long long;

int A[100100], B[100100], C[100100];
vector<bool> seen(100100, false);
vector<int> ans = {1}, pass(100100,0);

void dfs(int s, vector<vector<int>> &G){
  seen.at(s) = true;
  
  pass.at(C[s])++;
  for(auto next: G.at(s)){
    if(seen.at(next)) continue;
    if(pass.at(C[next]) == 0) ans.push_back(next);
    dfs(next,G);
  }
  pass.at(C[s])--;
  return;
}

int main(){
  int N;
  cin >> N;
  rep(i,1,N+1) cin >> C[i];
  rep(i,1,N) cin >> A[i] >> B[i];
    
  vector<vector<int>> graph(100100);
  rep(i,1,N){
    graph.at(A[i]).push_back(B[i]);
    graph.at(B[i]).push_back(A[i]);
  }
  
  dfs(1, graph);
  sort(ans.begin(), ans.end());
  for(auto x: ans) cout << x << endl;
}