#include <bits/stdc++.h>
using namespace std;
#define L 20
#define N 111111


int n;
int pre[N];
vector<int> adj[N];
int parent[N];
int height[N];
int anc[N][L];
int downj[N];
int down1[N];
int down2[N];
int up[N];


int ascend(int a, int d) {
    for (int k = 0; k < L; k++) {
        if (d == 0) break;
        if (d & 1) a = anc[a][k];
        d >>= 1;
    }
    return a;
}


int lca(int a, int b) {
    if (height[a] > height[b]) a = ascend(a, height[a] - height[b]);
    if (height[b] > height[a]) b = ascend(b, height[b] - height[a]);
    if (a == b) return a;
    for (int k = L-1; k >= 0; k--) {
        if (anc[a][k] != anc[b][k]) {
            a = anc[a][k];
            b = anc[b][k];
        }
    }
    return parent[a];
}


void prepare() {
    for (int i = 0; i < n; i++) {
        parent[i] = -1;
        downj[i] = -1;
        down1[i] = down2[i] = 1;
    }

    int q = 1;
    parent[0] = 0;
    height[0] = 0;
    for (int f = 0; f < n; f++) {
        int i = pre[f];
        anc[i][0] = parent[i];
        for (int k = 0; k < L-1; k++) {
            anc[i][k+1] = anc[anc[i][k]][k];
        }
        for (int nb = 0; nb < adj[i].size(); nb++) {
            int j = adj[i][nb];
            if (~parent[j]) continue;
            parent[j] = i;
            height[j] = height[i] + 1;
            pre[q++] = j;
        }
    }

    for (int f = n-1; f; f--) {
        int i = pre[f];
        int p = parent[i];
        int d = down1[i] + 1;
        if (down1[p] < d) {
            down2[p] = down1[p];
            down1[p] = d;
            downj[p] = i;
        } else if (down2[p] < d) {
            down2[p] = d;
        }
    }

    up[0] = 0;
    for (int f = 1; f < n; f++) {
        int i = pre[f];
        int p = parent[i];
        up[i] = max(up[p] + 1, (downj[p] == i ? down2 : down1)[p]);
    }
}


int answer_query(int t, int j) {
    if (t == j) return 0;
    int l = lca(t, j);
    int dist = height[t] + height[j] - height[l] * 2;
    int distj = dist - 1 >> 1;
    int distt = dist >> 1;
    return distt + (height[t] > height[j] ? up[ascend(t, distt)] : down1[ascend(j, distj)]);
}


void solve() {
    int q;
    scanf("%d%d", &n, &q);

    for (int i = 0; i < n; i++) {
        adj[i].clear();
    }

    for (int i = 1; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    prepare();
    while (q--) {
        int t, j;
        scanf("%d%d", &t, &j);
        printf("%d\n", answer_query(--t, --j));
    }
}


int main() {
    int z;
    scanf("%d", &z);
    while (z--) solve();
}