#pragma GCC optimize(2) #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int N = 5e5+10; int n,q,head[N],idx; pair<int,int> ans; struct Node{ int to,nex; }e[N<<1]; int read() { int s = 0; bool f = false; char c = getchar(); while (c < '0' || c > '9') f |= (c == '-'), c = getchar(); while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar(); return f ? -s : s; } void add_edge(int u,int v){ e[idx].to = v; e[idx].nex = head[u]; head[u] = idx++; } int dep[N],fa[N][20]; void dfs(int u,int f){ dep[u] = dep[f] + 1; fa[u][0] = f; for(int i = head[u];~i;i = e[i].nex){ if(e[i].to != f){ dfs(e[i].to,u); } } } void init(){ for(int k = 1;(1<<k) <= n;k++){ for(int i = 1;i <= n;i++){ fa[i][k] = fa[fa[i][k-1]][k-1]; } } } int lca(int u,int v){ if(dep[u] < dep[v]) swap(u,v); if(dep[u] != dep[v]){ for(int i = 19;i >= 0;i--){ if(dep[fa[u][i]] >= dep[v]) u = fa[u][i]; } } if(u == v) return u; for(int i = 19;i >= 0;i--){ if(fa[u][i] != fa[v][i]){ u = fa[u][i],v = fa[v][i]; } } return fa[u][0]; } void cal(int x,int y,int z){ int lca1 = lca(x,y); int distance = dep[x]+dep[y]-2*dep[lca1]; int lca2 = lca(lca1,z); distance += dep[lca1]+dep[z]-2*dep[lca2]; if(ans.second > distance){ ans.first = lca1; ans.second = distance; } } int main(){ n = read();q = read(); //scanf("%d%d",&n,&q); memset(head,-1,sizeof(head)); for(int i = 1;i < n;i++){ int u,v; u = read(),v = read(); //scanf("%d%d",&u,&v); add_edge(u,v);add_edge(v,u); } dfs(1,0); init(); while(q--){ int x,y,z; x = read(),y = read(),z = read(); //scanf("%d%d%d",&x,&y,&z); int u = lca(x,y); ans.first = -1,ans.second = inf; cal(x,y,z);cal(x,z,y);cal(y,z,x); printf("%d %d\n",ans.first,ans.second); } return 0; }