#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 500005; struct node{ int v, w, next; }E[MAX_N << 1]; int head[MAX_N], top = 0; inline void add(int u, int v) { E[++ top].v = v; E[top].w = 1; E[top].next = head[u]; head[u] = top; } int N, M, u, v, w; int go[MAX_N][20], deep[MAX_N], sum[MAX_N]; void dfs(int last, int x) { for (int i=head[x]; i; i=E[i].next){ if (E[i].v != last){ go[E[i].v][0] = x; deep[E[i].v] = deep[x] + 1; sum[E[i].v] = E[i].w + sum[x]; dfs(x, E[i].v); } } } void pre(void) { for (int k=1; k<=19; k++) for (int i=1; i<=N; i++) go[i][k] = go[go[i][k - 1]][k - 1]; } void goup(int &x, int k) { for (int i=19; i>=0; i--) if ((1<<i) & k) x = go[x][i]; } int LCA(int u, int v) { if (deep[u] > deep[v]) goup(u, deep[u] - deep[v]); if (deep[v] > deep[u]) goup(v, deep[v] - deep[u]); if (u == v) return u; for (int k=19; k>=0; k--) if (go[u][k] != go[v][k]) u = go[u][k], v = go[v][k]; return go[u][0]; } void doit(void) { while (M --){ scanf("%d%d%d", &u, &v, &w); int f1 = LCA(u, v), f2 = LCA(v, w), f3 = LCA(w, u); int r, ans = 0, another, a, b; if(deep[f1] < deep[f2]){ r = f2, another = u; a = v, b = w; } else { r = f1, another = w; a = u, b = v;} if(deep[r] < deep[f3]){ r = f3, another = v; a = u, b = w; } int fr = LCA(r, another); printf("%d %d\n", r, sum[a] + sum[b] - 2 * sum[r] + sum[r] + sum[another] - 2 * sum[fr]); } } int main(void) { scanf("%d%d", &N, &M); for (int i=1; i<=N-1; i++) scanf("%d%d", &u, &v), add(u, v), add(v, u); dfs(0, 1); pre(); doit(); return 0; }