// Animesh Fatehpuria #include "bits/stdc++.h" using namespace std; const int N = 1e5 + 50; const int LN = 20; int t, n, q; int val1[N], val2[N], dp1[N], dp2[N]; int depth[N], anc[LN][N]; vector < int > adj[N]; // DFS to set up important arrays inline void dfs1(int u, int p, int lvl) { depth[u] = lvl; for (int i = 1; i < LN; i++) { anc[i][u] = anc[i - 1][anc[i - 1][u]]; } for (int v : adj[u]) { if (v != p) { anc[0][v] = u; dfs1(v, u, lvl + 1); } } } // Tree DP to compute longest path in the same subtree inline void dfs2(int u, int p) { val1[u] = 0, val2[u] = 0; dp1[u] = -1, dp2[u] = -1; for (int v : adj[u]) { if (v != p) { dfs2(v, u); if (val1[v] + 1 > val1[u]) { swap(val1[u], val2[u]); swap(dp1[u], dp2[u]); val1[u] = val1[v] + 1; dp1[u] = v; } else if (val1[v] + 1 > val2[u]) { val2[u] = val1[v] + 1; dp2[u] = v; } } } } // Tree DP to compute longest path in the upperTree inline void dfs3(int u, int p, int upperTree) { if (upperTree > val1[u]) { swap(val1[u], val2[u]); swap(dp1[u], dp2[u]); val1[u] = upperTree; dp1[u] = p; } else if (upperTree > val2[u]) { val2[u] = upperTree; dp2[u] = p; } for (int v : adj[u]) { if (v != p) { if (dp1[u] == v) { dfs3(v, u, max(upperTree + 1, val2[u] + 1)); } else { dfs3(v, u, max(upperTree + 1, val1[u] + 1)); } } } } // Returns the lca of x and y inline int lca(int x, int y) { if (depth[x] < depth[y]) { swap(x, y); } for (int i = LN - 1; i >= 0; i--) { if (depth[x] - (1 << i) >= depth[y]) { x = anc[i][x]; } } if (x == y) { return x; } for (int i = LN - 1; i >= 0; i--) { if (anc[i][x] != anc[i][y]) { x = anc[i][x]; y = anc[i][y]; } } return anc[0][x]; } // Returns the distance between (u) and (v) inline int getDistance(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; } // Returns the k'th ancestor of (x) inline int getKthAncestor(int x, int k) { if (k == 0) { return x; } for (int i = LN - 1; i >= 0; i--) { if (k - (1 << i) >= 0) { x = anc[i][x]; k -= (1 << i); } } return x; } // Returns the k'th node on the path from x to y inline int getKthNode(int x, int y, int k) { int lc = lca(x, y); int leftChain = depth[x] - depth[lc] + 1; if (leftChain >= k) { return getKthAncestor(x, k - 1); } else { k -= leftChain; k += 1; int rightChain = depth[y] - depth[lc] + 1; return getKthAncestor(y, rightChain - k); } } // Returns Jerry's location in his optimal strategy inline int getJerryLocation(int x, int y) { int d = getDistance(x, y); int req = (d + 1) / 2; return getKthNode(x, y, req); } // Returns Tom's location in his optimal strategy inline int getTomLocation(int x, int y) { int d = getDistance(x, y); int req = (d + 1) / 2; return getKthNode(x, y, req + 1 + (1 - (d % 2))); } // Solve the query (jerryLocation, tomLocation) inline void solve(int x, int y) { if (x == y) { printf("0\n"); return; } int jerry = getJerryLocation(x, y); int tom = getTomLocation(x, y); int ans = getDistance(x, jerry) + (1 - (getDistance(x, y) % 2)); if (getDistance(dp1[jerry], tom) <= 1) { ans += val2[jerry]; } else { ans += val1[jerry]; } printf("%d\n", ans + 1); } int main() { scanf("%d", &t); while (t--) { scanf("%d %d", &n, &q); for (int i = 1; i <= n; i++) { adj[i].clear(); } for (int i = 1; i < n; i++) { int u, v; scanf("%d %d", &u, &v); adj[u].push_back(v); adj[v].push_back(u); } anc[0][1] = 1; dfs1(1, 0, 0); dfs2(1, 0); dfs3(1, 0, 0); while (q--) { int x, y; scanf("%d %d", &x, &y); solve(y, x); } } }