#include <bits/stdc++.h>
using namespace std;
int cnt_list, pos[20200], pa[20100], len[20100], fs[20100], pc[20100],
    ls[20100], cnt_ls, tmp[20100], cnt, n, num_q;
struct pp {
  int id;
  char ch;
};
vector<pp> adj[20201];
pp now;
void dfs(int id, int pr) {
  int i, j, s, p, q, ip;
  pos[id] = cnt_list++;
  pa[pos[id]] = pr;
  for (i = 0; i < adj[id].size(); i++) {
    ip = adj[id][i].id;
    if (pos[ip] >= 0) continue;
    pc[cnt_list] = adj[id][i].ch - 'a';
    dfs(ip, pos[id]);
  }
}
int main() {
  int id1, id2, i, j, s, p, q, x, y, fg;
  char ch;
  scanf("%d%d", &n, &num_q);
  for (i = 0; i < n - 1; i++) {
    scanf("%d%d", &id1, &id2);
    ch = getchar();
    while (ch < 'a' || ch > 'z') ch = getchar();
    id1--;
    id2--;
    now.id = id2;
    now.ch = ch;
    adj[id1].push_back(now);
    now.id = id1;
    now.ch = ch;
    adj[id2].push_back(now);
  }
  memset(pos, -1, sizeof(pos));
  dfs(0, -1);
  while (num_q--) {
    scanf("%d%d", &x, &y);
    x--;
    y--;
    x = pos[x];
    y = pos[y];
    int u, v;
    u = x;
    v = y;
    cnt_ls = cnt = 0;
    while (u != v) {
      if (u > v) {
        ls[cnt_ls++] = pc[u];
        u = pa[u];
      } else {
        tmp[cnt++] = pc[v];
        v = pa[v];
      }
    }
    while (cnt > 0) ls[cnt_ls++] = tmp[--cnt];
    for (i = 0; i < n; i++) len[i] = -1;
    u = x;
    fs[u] = len[u] = 0;
    int ans = 0;
    while (u != 0) {
      len[pa[u]] = len[u] + 1;
      if (fs[u] == 0) {
        if (len[u] < cnt_ls) {
          if (ls[len[u]] > pc[u])
            fs[pa[u]] = -1;
          else if (ls[len[u]] < pc[u])
            fs[pa[u]] = 1;
          else
            fs[pa[u]] = 0;
        } else
          fs[pa[u]] = 1;
      } else
        fs[pa[u]] = fs[u];
      if (fs[pa[u]] < 0 || (fs[pa[u]] == 0 && len[pa[u]] != cnt_ls)) ans++;
      u = pa[u];
    }
    for (i = 1; i < n; i++) {
      if (len[pa[i]] >= 0 && len[i] < 0) {
        len[i] = len[pa[i]] + 1;
        if (fs[pa[i]] == 0) {
          if (len[pa[i]] < cnt_ls) {
            if (ls[len[pa[i]]] > pc[i])
              fs[i] = -1;
            else if (ls[len[pa[i]]] < pc[i])
              fs[i] = 1;
            else
              fs[i] = 0;
          } else
            fs[i] = 1;
        } else
          fs[i] = fs[pa[i]];
        if (fs[i] < 0 || (fs[i] == 0 && len[i] != cnt_ls)) ans++;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}
