1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <cstring>
  6 #include <algorithm>
  7 #include <queue>
  8 #include <stack>
  9 #include <vector>
 10 #include <set>
 11 #include <map>
 12 #define MP(a, b) make_pair(a, b)
 13 #define PB(a) push_back(a)
 14 
 15 using namespace std;
 16 
 17 typedef long long ll;
 18 typedef pair<int ,int> pii;
 19 typedef pair<unsigned int, unsigned int> puu;
 20 typedef pair<int ,double> pid;
 21 typedef pair<ll, int> pli;
 22 
 23 const int INF = 0x3f3f3f3f;
 24 const double eps = 1e-6;
 25 const int LEN = 100010;
 26 const int LOG_LEN = 22;
 27 vector<int> Map[LEN];
 28 map<string, int> mp;
 29 int ind[LEN], n ,m, root, depth[LEN], parent[LOG_LEN][LEN];
 30 
 31 void dfs(int v, int p, int d){
 32     parent[0][v] = p;
 33     depth[v] = d;
 34     for(int i=0; i<Map[v].size(); i++){
 35         if(Map[v][i]!=p) dfs(Map[v][i], v, d+1);
 36     }
 37 }
 38 
 39 void init(int n)
 40 {
 41     dfs(root, -1, 0);
 42     for(int k=0; k+1<LOG_LEN; k++){
 43         for(int i=0; i<n; i++){
 44             if(parent[k][i]<0) parent[k+1][i] = -1;
 45             else parent[k+1][i] = parent[k][parent[k][i]];
 46         }
 47     }
 48 }
 49 
 50 int lca(int u, int v)
 51 {
 52     int ret = 0;
 53     if(depth[u]>depth[v])swap(u, v);
 54     for(int k=0; k<LOG_LEN; k++){
 55         if((depth[v]-depth[u]) >> k & 1) v = parent[k][v];
 56     }
 57     if(u==v) return u;
 58     for(int k=LOG_LEN-1; k>=0; k--){
 59         if(parent[k][u]!=parent[k][v]){
 60             u = parent[k][u];
 61             v = parent[k][v];
 62         }
 63     }
 64     return parent[0][v];
 65 }
 66 
 67 int solve(int v, int p){
 68     int ret = 0;
 69     for(int i=LOG_LEN-1; i>=0; i--)
 70         if(parent[i][v]!=-1 && depth[parent[i][v]]>=depth[p]){
 71             v = parent[i][v];
 72             ret+=(1<<i);
 73         }
 74     return ret;
 75 }
 76 
 77 int main()
 78 {
 79 //    freopen("in.txt", "r", stdin);
 80 
 81     int T, a, b;
 82     char va[110], vb[110];
 83     scanf("%d", &T);
 84     while(T--){
 85         for(int i=0; i<LEN; i++)Map[i].clear();
 86         mp.clear();
 87         memset(ind, 0, sizeof ind);
 88         scanf("%d%d", &n, &m);
 89         int vcnt = 0;
 90         for(int i=0; i<n-1; i++){
 91             scanf("%s%s", va, vb);
 92             if(!mp.count(va)) mp[va] = vcnt++;
 93             if(!mp.count(vb)) mp[vb] = vcnt++;
 94             ind[mp[va]] ++;
 95             Map[mp[va]].PB(mp[vb]);
 96             Map[mp[vb]].PB(mp[va]);
 97         }
 98         for(int i=0; i<n; i++)if(!ind[i]){root = i;break;}
 99         init(n);
100         for(int i=0; i<m; i++){
101             scanf("%s%s", va, vb);
102             int lv = lca(mp[va], mp[vb]);
103             printf("%d\n", solve(mp[va], lv)+(lv==mp[vb]?0:1));
104         }
105     }
106     return 0;
107 }