6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6

5 2
2 5
4 1
6 0

Day1

 /**************************************************************

     Problem: 1787

     User: hahalidaxin2

     Language: C++

     Result: Accepted

     Time:3716 ms

     Memory:65216 kb

 ****************************************************************/

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<vector>

 #include<iostream>

 using namespace std;

 const int maxn = +;

 const int maxd = ;

 struct Edge{ int u,v;

 };

 vector<int> G[maxn];

 vector<Edge> es;

 int d[maxn];

 int p[maxn][maxd];

 void addedge(int u,int v) {

     es.push_back((Edge){u,v});

     int m=es.size(); G[u].push_back(m-);

 }

 void dfs(int u,int fa) {

     for(int i=;i<=maxd;i++) {       //构造倍增数组

         if(d[u]<(<<i)) break;

         p[u][i]=p[p[u][i-]][i-];

     }

     for(int i=;i<G[u].size();i++) {

         Edge e=es[G[u][i]]; int v=e.v;

         if(v!=fa)

             d[v]=d[u]+ , p[v][]=u , dfs(v,u);

     }

 }

 int lca(int u,int v) {

     if(d[v]>d[u]) swap(u,v);

     int dep=d[u]-d[v];

     for(int i=;i<maxd;i++)

         if((<<i)&dep) u=p[u][i];

     if(u==v) return u;

     for(int i=maxd-;i>=;i--)

         if(p[u][i]!=p[v][i])

             u=p[u][i] , v=p[v][i];

     return p[u][];

 }

 int dist(int x,int y) { return d[x]+d[y]-(d[lca(x,y)]<<); }

 int n,m;

 void read(int& x) {

     char c=getchar();

     while(!isdigit(c)) c=getchar();

     x=;

     while(isdigit(c))

         x=x*+c-'' , c=getchar();

 }

 int main() {

     read(n),read(m);

     int u,v;

     for(int i=;i<n-;i++) {

         read(u),read(v);

         addedge(u,v); addedge(v,u);

     }

     dfs(n>>,-);

     int a,b,c,lab,lac,lbc,s;

     while(m--) {

         read(a),read(b),read(c);

         lab=lca(a,b),lac=lca(a,c),lbc=lca(b,c);

         if(lab==lac) s=lbc;

         else if(lab==lbc) s=lac;

         else s=lab;

         printf("%d %d\n",s,dist(a,s)+dist(b,s)+dist(c,s));

     }

     return ;

 }