#include <bits/stdc++.h>
#define MAXP 18
using namespace std;

int n,m,q;
unordered_map<string,int> mp;

int e[200010][2],p[100010],col[100010];
int fa[100010][20],dep[100010];
int len[100010],pts[100010][2];

void adde(int sn,int fn,int id)
{
    e[id][0] = fn; e[id][1] = p[sn]; p[sn] = id;
}

void input()
{
    int i,sn,fn;
    string s;
    
    memset(p,0,sizeof(int)*(n+3));
    memset(len,0,sizeof(int)*(n+3));
    memset(pts,0,sizeof(pts[0])*(n+3));
    m = 0; mp.clear();
    
    for(i=1;i<=n;i++)
    {
        cin >> s;
        if(mp.find(s) == mp.end()) mp[s] = ++m;
        col[i] = mp[s]; 
    }
    
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&sn,&fn);
        adde(sn,fn,i<<1); adde(fn,sn,i<<1|1);
    }
}

int calcDis(int x,int y)
{
    int i,ret = 0;
    if(!x || !y) return 0;
    if(dep[x] < dep[y]) swap(x,y);
    for(i=MAXP;i>=0;i--) if(dep[fa[x][i]] >= dep[y])
        x = fa[x][i], ret += 1<<i;
    if(x == y) return ret;
    for(i=MAXP;i>=0;i--) if(fa[x][i] != fa[y][i])
        x = fa[x][i], y = fa[y][i], ret += 1<<(i+1);
    return ret+2;
}

void dfs(int sn,int pa,int d)
{
    int i,fn,c = col[sn];
    
    dep[sn] = d;
    for(i=1,fa[sn][0]=pa;i<=MAXP;i++)
        fa[sn][i] = fa[fa[sn][i-1]][i-1];
    
    if(!pts[c][0]) pts[c][0] = sn;
    else if(!pts[c][1]) pts[c][1] = sn, len[c] = calcDis(pts[c][0],sn);
    else
    {
        int d1 = calcDis(pts[c][0],sn), d2 = calcDis(pts[c][1],sn);
        if(d1>=d2 && d1>len[c]) pts[c][1] = sn, len[c] = d1;
        if(d2>=d1 && d2>len[c]) pts[c][0] = sn, len[c] = d2;
    }
    
    for(i=p[sn];i;i=e[i][1])
    {
        if((fn=e[i][0]) == pa) continue;
        dfs(fn,sn,d+1);
    }
}

int query(int x,int y)
{
    return max(max(calcDis(pts[x][0],pts[y][0]),
                   calcDis(pts[x][1],pts[y][0])),
               max(calcDis(pts[x][0],pts[y][1]),
                   calcDis(pts[x][1],pts[y][1])));
}

int main()
{
    int i,x,y;
    string s1,s2;
    
    while(scanf("%d%d",&n,&q)>0)
    {
        input();
        dfs(1,0,1);
        while(q--)
        {
            cin >> s1 >> s2;
            x = (mp.find(s1) == mp.end() ? -1 : mp[s1]);
            y = (mp.find(s2) == mp.end() ? -1 : mp[s2]);
            printf("%d\n",x<0||y<0?-1:query(x,y)+1);
        }
    }
    return 0;
}