TATAKAI

#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace std;

#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("avx2")

#define sync ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
#define unq(a) sort(all(a));a.resize(unique(all(a)) - a.begin())
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//mt19937 rng(7);
using pii = pair<int , int>;

int inline max(const int x, const int y){return (x > y ? x : y);}
int inline min(const int x, const int y){return (x < y ? x : y);}

const int base = 31;
const int mxn = 1e5 + 5, mod0 = 1e9 + 7, mod1 = 1e9 + 9;
vector<pii> g[mxn];
bitset<mxn> blocked;
int sz[mxn];
vector<int> dg[mxn];

int n, q;
const int LOG = 17;
int dep[mxn], par[LOG][mxn], ch[mxn];
int h0[mxn], ih0[mxn], h1[mxn], ih1[mxn], tw0[mxn], itw0[mxn], tw1[mxn], itw1[mxn];

void pre(){
    for (int i = 1;i < LOG;i++){
        for (int j = 1;j <= n;j++){
            par[i][j] = par[i - 1][par[i - 1][j]];
        }
    }
}

int inline jump(int x, int d){
    for (int i = 0; i < LOG;i++){
        if (d & (1 << i)){
            x = par[i][x];
        }
    }
    return x;
}

int inline lca(int u, int v){
    if (dep[u] < dep[v]) swap(u , v);
    u = jump(u , dep[u] - dep[v]);
    if (u == v) return u;
    for (int i = LOG - 1;i >= 0;i--){
        if (par[i][u] == par[i][v]) continue;
        u = par[i][u]; v = par[i][v];
    }
    return par[0][u];
}

void dfs0(int cur, int p, ll l){
    h0[cur] = (h0[p] + tw0[l] * 1ll * ch[cur]) % mod0;
    ih0[cur] = (ih0[p] + itw0[l] * 1ll * ch[cur]) % mod0;

    h1[cur] = (h1[p] + tw1[l] * 1ll * ch[cur]) % mod1;
    ih1[cur] = (ih1[p] + itw1[l] * 1ll * ch[cur]) % mod1;

    dep[cur] = l;
    par[0][cur] = p;
    for (const pair<int , int>& x : g[cur]){
        if (x.fi == p) continue;
        dfs0(x.fi, cur, l + x.se);
    }
}

int inline power(ll x, ll y, ll md = mod0){
    ll r = 1;
    while(y > 0){
        if (y & 1){
            r = (r * x) % md;
        }
        y >>= 1;
        x = (x * x) % md;
    }
    return r;
}


int root;
int get_centroid(int cur, int p){
    int mx = sz[root] - sz[cur], to = -1;
    for (const pii& nxt : g[cur]){
        int x = nxt.fi;
        if (blocked[x] or x == p) continue;
        if (sz[x] > mx){
            mx = sz[x];
            to = x;
        }
    }
    if (mx <= sz[root] / 2){
        return cur;
    }
    return get_centroid(to , cur);
}
int plink[mxn];

void dfs(int cur, int p){
    sz[cur] = 1;
    for (const pii& nxt : g[cur]){
        int x = nxt.fi;
        if (blocked[x] or x == p) continue;
        dfs(x, cur);
        sz[cur] += sz[x];
    }
}

int decompose(int cur){
    dfs(cur , 0);
    root = cur;
    int centroid = get_centroid(cur , 0);
    blocked[centroid] = 1;

    for (const pii& nxt : g[centroid]){
        int x = nxt.fi;
        if (blocked[x]) continue;
        dg[centroid].push_back(decompose(x));
        plink[dg[centroid].back()] = centroid;
    }
    return centroid;
}

int inline get_dis(int x, int y){
    return dep[x] + dep[y] - 2 * dep[lca(x , y)];
}

struct Query{
    int id, u, d;
    Query(){}
    Query(int _x, int _y, int _z){
        id = _x;
        u = _y;
        d = _z;
    }
};

struct Path_hash{
    bool inv;
    int u, v, lc, x, hsh0, hsh1, hingdis;
    Path_hash(pii p){
        u = p.fi; v = p.se; lc = lca(u , v);
        inv = (dep[u] > dep[lc] ? 0 : 1);
        hingdis = dep[u] - dep[lc] + 1;
    }
    pii get(int d){
        if (inv){
            int s = par[0][u];
            d = (dep[v] - dep[u] + 1) - d;
            x = jump(v , d);
            hsh0 = ((h0[x] - h0[s]) * 1ll * itw0[dep[u]]) % mod0;
            hsh0 %= mod0; if (hsh0 < 0) hsh0 += mod0;
            hsh1 = ((h1[x] - h1[s]) * 1ll * itw1[dep[u]]) % mod1;
            hsh1 %= mod1; if (hsh1 < 0) hsh1 += mod1;
        }
        else{
            if (d <= hingdis){
                x = jump(u , d);
                hsh0 = (ih0[u] * 1ll * tw0[dep[u]]) % mod0 - (ih0[x] * 1ll * tw0[d + dep[x]]) % mod0;
                hsh0 %= mod0; if (hsh0 < 0) hsh0 += mod0;
                hsh1 = (ih1[u] * 1ll * tw1[dep[u]]) % mod1 - (ih1[x] * 1ll * tw1[d + dep[x]]) % mod1;
                hsh1 %= mod1; if (hsh1 < 0) hsh1 += mod1;
            }
            else{
                int dd = hingdis;
                x = par[0][lc];
                hsh0 = (ih0[u] * 1ll * tw0[dep[u]]) % mod0 - (ih0[x] * 1ll * tw0[dd + dep[x]]) % mod0;
                hsh0 %= mod0; if (hsh0 < 0) hsh0 += mod0;
                hsh1 = (ih1[u] * 1ll * tw1[dep[u]]) % mod1 - (ih1[x] * 1ll * tw1[dd + dep[x]]) % mod1;
                hsh1 %= mod1; if (hsh1 < 0) hsh1 += mod1;

                d -= dd;
                dd = dep[v] - dep[lc];
                d = dd - d;
                assert(d >= 0);
                x = jump(v , d);
                hsh0 += ((h0[x] - h0[lc]) * 1ll * (hingdis > dep[lc] ? tw0[hingdis - dep[lc] - 1] : itw0[dep[lc] + 1 - hingdis])) % mod0;
                hsh0 %= mod0; if (hsh0 < 0) hsh0 += mod0;
                hsh1 += ((h1[x] - h1[lc]) * 1ll * (hingdis > dep[lc] ? tw1[hingdis - dep[lc] - 1] : itw1[dep[lc] + 1 - hingdis])) % mod1;
                hsh1 %= mod1; if (hsh1 < 0) hsh1 += mod1;
            }
        }
        return {hsh0, hsh1};
    }
    int inline encode(){
        return get(get_dis(u , v) + 1).fi;
    }
};

struct Path{
    int start, end, lc;
    Path() : start(0), end(0), lc(0) {}
    Path(int s, int e){
        start = s;
        end = e;
        lc = lca(s , e);
    }

    int inline at(int d){
        int u = start, v = end;
        if (dep[u] > dep[lc]){
            if (d <= dep[u] - dep[lc] + 1){
                return jump(u , d - 1);
            }
            else{
                d -= (dep[u] - dep[lc] + 1);
                d = dep[v] - dep[lc] - d;
                return jump(v , d);
            }
        }
        else{
            d = dep[v] - dep[u] + 1 - d;
            return jump(v , d);
        }
    }

    Path LexLess(Path& p0, Path& p1){
        Path_hash h0(pii{p0.start , p0.end}), h1(pii{p1.start , p1.end});
        int lo, hi, md, ix = -1;
        lo = 1; hi = min(get_dis(p0.start , p0.end) , get_dis(p1.start , p1.end)) + 1;
        while(lo <= hi){
            md = (lo + hi) / 2;
            if (h0.get(md) != h1.get(md)){
                ix = md;
                hi = md - 1;
            }
            else{
                lo = md + 1;
            }
        }
        if (~ix) return (ch[p0.at(ix)] < ch[p1.at(ix)] ? p0 : p1);
        return (get_dis(p0.start , p0.end) < get_dis(p1.start , p1.end) ? p0 : p1);
    }
};

vector<Query> Q[mxn];
vector<Query> qe[mxn];
bitset<mxn> bt;
Path s[mxn];
vector<pair<Path , Path>> ans_candidates[mxn];

void AddQ(int id, int u, int d){
    int cur = u;
    while(cur){
        int nd = get_dis(u, cur) + 1;
        if (d >= nd){
            Q[cur].push_back(Query(id, u, d));
        }
        cur = plink[cur];
    }
}

void mdfs(int cur, int p, int l, vector<pair<int , Path>>& dt){
    int curd = get_dis(root , cur) + 1;
    dt.push_back({curd, Path(root , cur)});
    Path prf(cur , root);
    for (const Query& q : qe[cur]){
        int d = q.d - curd + 1;
        if (bt[d]){
            ans_candidates[q.id].push_back({prf , s[d]});
        }
    }
    for (const int& x : dg[cur]){
        if (cur == p) continue;
        mdfs(x, cur, l + 1, dt);
    }
}

void Solve(int R){
    if (!Q[R].size()) return;
    vector<Query>& q = Q[R];
    root = R;

    for (const Query& w : q){
        qe[w.u].push_back(w);
    }

    bt[1] = 1;
    s[1] = Path(R , R);

    vector<int> idx;
    vector<pair<int , Path>> subdt;
    for (const int& c : dg[R]){
        subdt.clear();
        mdfs(c, R, 1, subdt);
        for (pair<int , Path>& dt : subdt){
            if (bt[dt.fi]) s[dt.fi] = s[dt.fi].LexLess(s[dt.fi] , dt.se);
            else s[dt.fi] = dt.se, bt[dt.fi] = 1, idx.push_back(dt.fi);
        }
    }

    for (const Query& q : qe[R]){
        int d = q.d;
        if (bt[d]){
            ans_candidates[q.id].push_back({Path(R , R) , s[d]});
        }
    }

    for (const int& x : idx) bt[x] = 0;
    reverse(all(dg[R]));

    idx.clear();
    for (const int& c : dg[R]){
        subdt.clear();
        mdfs(c, R, 1, subdt);
        for (pair<int , Path>& dt : subdt){
            if (bt[dt.fi]) s[dt.fi] = s[dt.fi].LexLess(s[dt.fi] , dt.se);
            else s[dt.fi] = dt.se, bt[dt.fi] = 1, idx.push_back(dt.fi);
        }
    }

    for (const Query& q : qe[R]){
        int d = q.d;
        if (bt[d]){
            ans_candidates[q.id].push_back({Path(R , R) , s[d]});
        }
    }

    for (const int& x : idx) bt[x] = 0;
    bt[1] = 0;
    for (const Query& w : q){
        qe[w.u].clear();
    }
}

int main(){

    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    sync

    int t = 1;
    scanf("%d", &t);

    int a = power(base , mod0 - 2, mod0), b = power(base, mod1 - 2, mod1);
    tw0[0] = tw1[0] = itw0[0] = itw1[0] = 1;
    for (int i = 1; i < mxn; i++){
        tw0[i] = (tw0[i - 1] * 1ll * base) % mod0;
        tw1[i] = (tw1[i - 1] * 1ll * base) % mod1;

        itw0[i] = (itw0[i - 1] * 1ll * a) % mod0;
        itw1[i] = (itw1[i - 1] * 1ll * b) % mod1;
    }

    while(t--){
        scanf("%d%d", &n, &q);
        char c;
        for (int i = 1; i <= n; i++){
            scanf(" %c", &c);
            ch[i] = (c - 'a') + 1;
        }

        for (int u, v, w, i = 0; i < n - 1; i++){
            scanf("%d%d", &u, &v);
            w = 1;
            g[u].push_back({v, w});
            g[v].push_back({u, w});
        }

        dfs0(1, 0, 1);
        pre();
        decompose(1);

        for (int u, d, i = 0; i < q; i++){
            scanf("%d%d", &u, &d);
            AddQ(i, u, d);
        }

        for (int i = 1; i <= n; i++) Solve(i);
        for (int i = 0; i < q; i++){
            if (ans_candidates[i].size()){
                Path res(ans_candidates[i][0].fi.start , ans_candidates[i][0].se.end), tmp;
                for (int j = 1; j < ans_candidates[i].size(); j++){
                    tmp = Path(ans_candidates[i][j].fi.start , ans_candidates[i][j].se.end);
                    res = res.LexLess(res , tmp);
                }
                cout << Path_hash({res.start , res.end}).encode() << endl;
            }
            else{
                cout << -1 << endl;
            }
        }
        for (int i = 0; i <= n; i++) g[i].clear(), dg[i].clear(), Q[i].clear(), blocked[i] = 0, plink[i] = 0;
        for (int i = 0; i <= q; i++) ans_candidates[i].clear();
    }
    cerr << "processor time: " << clock() / (double) CLOCKS_PER_SEC << "s    ";
    return 0;
}