#include using namespace std; #define L 20 #define N 111111 int n; int pre[N]; vector 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(); }