#include "bits/stdc++.h"
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;

int N;
vector<int> C;
vector<vector<int>> T;

void input(){
    cin >> N;
    C.resize(N);
    REP(i,N) cin >> C[i];
    T.resize(N);
    REP(i,N-1){
        int A,B;
        cin >> A >> B;
        A--; B--;
        T[A].push_back(B);
        T[B].push_back(A);
    }
}

void DFS(int s,vector<bool> &flag,vector<int> &memo,priority_queue<int,vector<int>,greater<int>> &res){
    flag[s] = true;
    if(memo[C[s]] == 0) res.push(s);
    memo[C[s]]++;
    for(auto v : T[s]){
        if(!flag[v]) DFS(v,flag,memo,res);
    }
    memo[C[s]]--;
}

int main(){
    input();
    vector<bool> flag(N,false);
    vector<int> memo(100010,0);
    priority_queue<int,vector<int>,greater<int>> res;
    DFS(0,flag,memo,res);
    while(!res.empty()){
        cout << res.top()+1 << endl;
        res.pop();
    }
    return 0;
}
/*
author: Yash Gupta
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define IOS                  \
	ios::sync_with_stdio(0); \
	cin.tie(0);              \
	cout.tie(0);
#define endl "\n"
#define mem(x, y) memset(x, y, sizeof(x))
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
const int N = 2e5 + 5;
const int inf = 9e18 + 9;
const int mod = 1e9 + 7;
struct node
{
	int x, y;
};
int n, m;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
vector<vector<node>> v(26, vector<node>{});
bool vis[2005][2005];
int dist[2005][2005];
vector<bool> used(26, false);
char a[2005][2005];
bool check(node p)
{
	if (vis[p.x][p.y])
		return false;
	if (a[p.x][p.y] == '#')
		return false;
	if (p.x < 0 || p.y < 0)
		return false;
	if (p.x >= n || p.y >= m)
		return false;
	return true;
}
void solve()
{
	mem(vis, false);
	mem(dist, 0);
	cin >> n >> m;
	node start, end;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
			if (a[i][j] == 'S')
			{
				start = {i, j};
			}
			else if (a[i][j] == 'G')
			{
				end = {i, j};
			}
			else if (a[i][j] == '#')
			{
				vis[i][j] = true;
			}
			else if (a[i][j] == '.')
			{
				continue;
			}
			else
			{
				v[a[i][j] - 'a'].pb({i, j});
			}
		}
	}
	queue<node> q;
	q.push(start);
	vis[start.x][start.y] = true;
	dist[start.x][start.y] = 0;
	bool f = false;
	while (!q.empty())
	{
		node curr = q.front();
		q.pop();
		if (end.x == curr.x && end.y == curr.y)
		{
			f = true;
			break;
		}
		else
		{
			for (int i = 0; i < 4; i++)
			{
				if (check({curr.x + dx[i], curr.y + dy[i]}))
				{
					q.push({curr.x + dx[i], curr.y + dy[i]});
					vis[curr.x + dx[i]][curr.y + dy[i]] = true;
					dist[curr.x + dx[i]][curr.y + dy[i]] = 1 + dist[curr.x][curr.y];
				}
			}
			if (a[curr.x][curr.y] != 'S' && a[curr.x][curr.y] != '.' && !used[a[curr.x][curr.y] - 'a'])
			{
				used[a[curr.x][curr.y] - 'a'] = true;
				for (auto p : v[a[curr.x][curr.y] - 'a'])
				{
					if (!vis[p.x][p.y])
					{
						q.push(p);
						vis[p.x][p.y] = true;
						dist[p.x][p.y] = 1 + dist[curr.x][curr.y];
					}
				}
			}
		}
	}
	if (f)
	{
		cout << dist[end.x][end.y] << endl;
	}
	else
	{
		cout << "-1" << endl;
	}
}

int32_t main()
{
	IOS;
	int t = 1;
	// cin>>t;
	for (int i = 1; i <= t; i++)
	{
		solve();
	}
}