#include <bits/stdc++.h>
using namespace std;
const int p = 131, mod = 998244353;
int head[20005], nxt[40005], pnt[40005], len[40005], E, bz[20005][20],
    pw[20005];
int bz1[20005][15], bz2[20005][15], rt, maxn, dep[20005], siz[20005],
    vis[20005];
int bel[20005], LL[20005], RR[20005], ans[20005], n, q, inv[20005], belt[20005],
    nt;
int sum[20005];
int mo(int x) {
  if (x < 0) x += mod;
  if (x >= mod) x -= mod;
  return x;
}
void add_edge(int u, int v, int w) {
  pnt[E] = v;
  nxt[E] = head[u];
  len[E] = w;
  head[u] = E++;
}
vector<pair<int, int> > V[20005];
struct node {
  int u, v, id;
};
int ksm(int a, int p) {
  int ans = 1;
  while (p) {
    if (p & 1) ans = 1ll * ans * a % mod;
    a = 1ll * a * a % mod;
    p >>= 1;
  }
  return ans;
}
vector<node> Q;
int gethash(int u, int v) {
  int flag = 0, ans = 0, len = 0;
  if (dep[u] < dep[v]) flag = 1, swap(u, v);
  for (int i = 14; i >= 0; i--) {
    if (dep[bz[u][i]] >= dep[v]) {
      if (!flag)
        ans = mo(1ll * ans * pw[1 << i] % mod + bz1[u][i]);
      else
        ans = mo(1ll * bz2[u][i] * pw[len] % mod + ans);
      u = bz[u][i];
      len += 1 << i;
    }
  }
  return ans;
}
int jump(int u, int len) {
  for (int i = 14; i >= 0; i--)
    if (len & (1 << i)) u = bz[u][i];
  return u;
}
int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 14; i >= 0; i--)
    if (dep[bz[u][i]] >= dep[v]) u = bz[u][i];
  if (u == v) return u;
  for (int i = 14; i >= 0; i--)
    if (bz[u][i] != bz[v][i]) u = bz[u][i], v = bz[v][i];
  return bz[u][0];
}
int dis(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
int jump(int u, int v, int w) {
  if (w < 0) return -1;
  int LCA = lca(u, v);
  if (dep[u] - dep[LCA] >= w)
    return jump(u, w);
  else
    return jump(v, dis(u, v) - w);
}
int getval(int u, int v, int len) {
  int LCA = lca(u, v);
  if (dep[u] - dep[LCA] >= len)
    return bz1[jump(u, len - 1)][0];
  else
    return bz1[jump(v, dis(u, v) - len)][0];
}
int get(int u, int v, int len) {
  int LCA = lca(u, v);
  if (len <= dep[u] - dep[LCA])
    return gethash(u, jump(u, len));
  else {
    int lenn = dis(u, v) - len;
    return mo(1ll * gethash(u, LCA) * pw[len - (dep[u] - dep[LCA])] % mod +
              gethash(LCA, jump(v, lenn)));
  }
}
int lcp(int u1, int v1, int u2, int v2) {
  int L = 1, R = min(dis(u1, v1), dis(u2, v2)), ans = 0;
  while (L <= R) {
    int mid = (L + R) >> 1;
    if (get(u1, v1, mid) == get(u2, v2, mid))
      ans = mid, L = mid + 1;
    else
      R = mid - 1;
  }
  return ans;
}
struct trie {
  int rt[20005], rt1[20005], bz[640005][15], id[640005], T, dep[640005], tot;
  int val[640005], siz[640005], sum[640005], vis[640005], tree[640005][30];
  int ans[640005];
  int insert(int u, int w) {
    if (!tree[u][w]) tree[u][w] = ++tot;
    ans[tree[u][w]]++;
    return tree[u][w];
  }
  void dfs(int u, int &tot) {
    tot += ans[u];
    siz[id[u]] = tot;
    for (int i = 1; i < 15; i++) bz[id[u]][i] = bz[bz[id[u]][i - 1]][i - 1];
    for (int i = 1; i <= 26; i++) {
      if (tree[u][i]) {
        int v = tree[u][i];
        id[v] = ++T;
        vis[id[u]] = 1;
        val[id[v]] = i;
        bz[id[v]][0] = id[u];
        dep[id[v]] = dep[id[u]] + 1;
        sum[id[v]] = mo(1ll * sum[id[u]] * p % mod + i);
        dfs(v, tot);
      }
    }
  }
  int lcp(int u, int v, int pos) {
    int LCA = lca(u, v), maxx = min(dep[pos], ::dep[u] - ::dep[LCA]), now = 0;
    int tmppos = pos;
    for (int i = 14; i >= 0; i--)
      if (dep[bz[tmppos][i]] >= maxx) tmppos = bz[tmppos][i];
    int stck[20], stck1[20], stck2[20], top = 0, top1 = 0, top2 = 0,
                                        tmpppos = tmppos;
    int tmp = dep[pos] - dep[tmppos];
    for (int i = 0; i <= 14; i++)
      if (maxx & (1 << i)) stck[++top] = tmppos, tmppos = bz[tmppos][i];
    bool flag = 0;
    int tot = 0;
    for (int i = 14; i >= 0; i--) {
      if (now + (1 << i) <= maxx) {
        int tmp1 = bz1[u][i];
        int tmp2 =
            sum[stck[top]] - 1ll * sum[bz[stck[top]][i]] * pw[1 << i] % mod;
        tmp2 = mo(tmp2);
        if (tmp1 == tmp2) {
          tot = mo(1ll * tot * pw[1 << i] % mod + tmp1);
          now += (1 << i);
          u = ::bz[u][i];
          top--;
        } else {
          for (i = i - 1; i >= 0; i--) {
            tmp1 = mo(1ll * tot * pw[1 << i] % mod + ::bz1[u][i]);
            tmp2 = sum[bz[stck[top]][i]];
            if (tmp1 == tmp2) {
              now += (1 << i);
              tot = mo(1ll * tot * pw[1 << i] % mod + ::bz1[u][i]);
              u = ::bz[u][i];
            } else
              stck[top] = bz[stck[top]][i];
          }
        }
      }
    }
    if (now != maxx) return now;
    maxx = min(tmp, dis(u, v));
    int ntmp = dis(u, v) - maxx;
    for (int i = 14; i >= 0; i--)
      if (ntmp & (1 << i)) v = ::bz[v][i];
    ntmp = tmp - maxx;
    for (int i = 14; i >= 0; i--)
      if (ntmp & (1 << i)) pos = bz[pos][i];
    for (int i = 0; i <= 14; i++) {
      if (maxx & (1 << i)) {
        stck1[++top1] = pos, stck2[++top2] = v;
        v = ::bz[v][i], pos = bz[pos][i];
      }
    }
    int noww = 0;
    for (int i = 14; i >= 0; i--) {
      if (noww + (1 << i) <= maxx) {
        int tmp1 = mo(sum[stck1[top1]] -
                      1ll * sum[bz[stck1[top1]][i]] * pw[1 << i] % mod);
        int tmp2 = mo(::sum[stck2[top2]] -
                      1ll * ::sum[::bz[stck2[top2]][i]] * pw[1 << i] % mod);
        if (tmp1 == tmp2) {
          noww += (1 << i);
          top1--, top2--;
        } else {
          int tmp = i, tmpp = 0;
          int tmpp1 = sum[bz[stck1[top1]][i]];
          int tmpp2 = ::sum[::bz[stck2[top2]][i]];
          for (i = i - 1; i >= 0; i--) {
            tmp2 = mo(::sum[::bz[stck2[top2]][i]] -
                      1ll * tmpp2 * pw[tmpp + (1 << i)] % mod);
            tmp1 = mo(sum[bz[stck1[top1]][i]] -
                      1ll * tmpp1 * pw[tmpp + (1 << i)] % mod);
            if (tmp1 == tmp2)
              noww += (1 << i), tmpp += (1 << i);
            else {
              stck1[top1] = bz[stck1[top1]][i];
              stck2[top2] = ::bz[stck2[top2]][i];
            }
          }
        }
      }
    }
    return now + noww;
  }
  int query(int u, int v, int L, int R) {
    int ans = 0, len = dis(u, v);
    while (L <= R) {
      int mid = (L + R) >> 1;
      int LCP = lcp(u, v, mid);
      if (LCP == len)
        R = mid - 1;
      else if (LCP == dep[mid]) {
        ans = mid;
        L = mid + 1;
      } else {
        int tmp1 = getval(u, v, LCP + 1), tmp2, tmppos = mid, tmp = LCP + 1;
        for (int i = 14; i >= 0; i--)
          if (dep[bz[tmppos][i]] >= tmp) tmppos = bz[tmppos][i];
        tmp2 = val[tmppos];
        if (tmp2 < tmp1) {
          ans = mid;
          L = mid + 1;
        } else
          R = mid - 1;
      }
    }
    if (!ans) return 0;
    return siz[ans];
  }
} tree;
void dfs(int u, int pre) {
  dep[u] = dep[pre] + 1;
  bz[u][0] = pre;
  siz[u] = 1;
  for (int i = 1; i < 15; i++) {
    bz[u][i] = bz[bz[u][i - 1]][i - 1];
    bz1[u][i] = mo(1ll * bz1[u][i - 1] * pw[(1 << i - 1)] % mod +
                   bz1[bz[u][i - 1]][i - 1]);
    bz2[u][i] = mo(1ll * bz2[bz[u][i - 1]][i - 1] * pw[(1 << i - 1)] % mod +
                   bz2[u][i - 1]);
  }
  for (int i = head[u]; i != -1; i = nxt[i]) {
    int v = pnt[i];
    if (v == pre) continue;
    bz1[v][0] = bz2[v][0] = len[i];
    sum[v] = mo(1ll * sum[u] * p % mod + len[i]);
    dfs(v, u);
    siz[u] += siz[v];
  }
}
void dfs1(int u, int pre, int tot) {
  int maxson = 0;
  siz[u] = 1;
  for (int i = head[u]; i != -1; i = nxt[i]) {
    int v = pnt[i];
    if (v == pre || vis[v]) continue;
    dfs1(v, u, tot);
    maxson = max(maxson, siz[v]);
    siz[u] += siz[v];
  }
  maxson = max(maxson, tot - siz[u]);
  if (maxson < maxn) rt = u, maxn = maxson;
  for (int i = 0; i < V[u].size(); i++)
    Q.push_back((node){u, V[u][i].first, V[u][i].second});
}
void dfs2(int u, int pre, int p1, int p2, int from) {
  belt[u] = nt;
  bel[u] = from;
  siz[u] = 1;
  for (int i = head[u]; i != -1; i = nxt[i]) {
    int v = pnt[i];
    if (v == pre || vis[v]) continue;
    dfs2(v, u, tree.insert(p1, len[i]), tree.insert(p2, len[i]), from);
    siz[u] += siz[v];
  }
}
void solve(int u, int tot) {
  nt++;
  Q.clear();
  maxn = 1e9;
  rt = 0;
  dfs1(u, 0, tot);
  tree.rt[rt] = ++tree.tot;
  tree.ans[tree.rt[rt]] = 1;
  int tt = tot;
  bel[rt] = rt;
  belt[rt] = nt;
  for (int i = head[rt]; i != -1; i = nxt[i]) {
    int v = pnt[i];
    if (vis[v]) continue;
    tree.rt1[v] = ++tree.tot;
    dfs2(v, rt, tree.insert(tree.rt[rt], len[i]),
         tree.insert(tree.rt1[v], len[i]), v);
  }
  tot = 0;
  LL[rt] = tree.id[tree.rt[rt]] = ++tree.T;
  tree.dfs(tree.rt[rt], tot);
  RR[rt] = tree.T;
  for (int i = head[rt]; i != -1; i = nxt[i]) {
    int v = pnt[i];
    if (vis[v]) continue;
    LL[v] = tree.id[tree.rt1[v]] = ++tree.T;
    tot = 0;
    tree.dfs(tree.rt1[v], tot);
    RR[v] = tree.T;
  }
  tot = tt;
  for (int i = 0; i < Q.size(); i++) {
    int U = Q[i].u, v = Q[i].v, id = Q[i].id;
    int LCP = lcp(U, v, U, rt);
    if (LCP == dis(U, v) && LCP != dis(U, rt))
      continue;
    else if (LCP == dis(U, rt)) {
      int w = jump(U, v, LCP);
      int tmp1 = tree.query(w, v, LL[rt], RR[rt]);
      int tmp2 = 0, pos = jump(U, rt, dis(U, rt) - 1);
      if (pos != -1 && belt[pos] == nt)
        tmp2 = tree.query(w, v, LL[bel[pos]], RR[bel[pos]]);
      ans[id] += tmp1 - tmp2;
    } else {
      int tmp1 = getval(U, v, LCP + 1), tmp2 = getval(U, rt, LCP + 1);
      int pos = jump(U, rt, dis(U, rt) - 1);
      if (tmp1 > tmp2) ans[id] += tot;
      if (tmp1 > tmp2 && pos != -1 && belt[pos] == nt) ans[id] -= siz[bel[pos]];
    }
  }
  vis[rt] = 1;
  for (int i = head[rt]; i != -1; i = nxt[i]) {
    int v = pnt[i];
    if (vis[v]) continue;
    solve(v, siz[v]);
  }
}
int main() {
  memset(head, -1, sizeof(head));
  cin >> n >> q;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    char w = getchar();
    while (!isalpha(w)) w = getchar();
    add_edge(u, v, w - 'a' + 1);
    add_edge(v, u, w - 'a' + 1);
  }
  pw[0] = 1;
  for (int i = 1; i <= 20000; i++) pw[i] = 1ll * pw[i - 1] * p % mod;
  inv[20000] = ksm(pw[20000], mod - 2);
  for (int i = 19999; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * p % mod;
  dfs(1, 0);
  for (int i = 1; i <= q; i++) {
    int u, v;
    cin >> u >> v;
    V[u].push_back(make_pair(v, i));
  }
  maxn = 1e9;
  dfs1(1, 0, n);
  solve(rt, n);
  for (int i = 1; i <= q; i++) cout << ans[i] - 1 << '\n';
}
