1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 500000+100014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 using namespace std;22 inline int read()23 {24     int x=0,f=1;char ch=getchar();25     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}26     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}27     return x*f;28 }29 int n,m,tot,ans,pos,head[maxn],dep[maxn],f[maxn][22];30 struct edge{int next,go;}e[2*maxn];31 void insert(int x,int y)32 {33     e[++tot].go=y;e[tot].next=head[x];head[x]=tot;34 }35 void dfs(int x)36 {37     for1(i,20)38      if(dep[x]>=(1<<i))39      f[x][i]=f[f[x][i-1]][i-1];40      else break;41     for(int i=head[x],y;i;i=e[i].next)42      if(dep[y=e[i].go]==-1) 43       {44           dep[y]=dep[x]+1;45           f[y][0]=x;46           dfs(y);47       }48 }49 int lca(int x,int y)50 {51     if(dep[x]<dep[y])swap(x,y);52     int t=dep[x]-dep[y];53     for0(i,20)54      if(t&(1<<i))55       x=f[x][i];56     if(x==y)return x;57     for(int i=20;i>=0;i--)58      if(f[x][i]!=f[y][i])59       x=f[x][i],y=f[y][i];60     return f[x][0];    61 }62 void update(int x,int y,int z)63 {64     int t=lca(x,y),tt=lca(t,z),ttt=dep[x]+dep[y]+dep[z]-dep[t]-2*dep[tt];65     if(ttt<ans)ans=ttt,pos=t;66 }67 int main()68 {69     freopen("input.txt","r",stdin);70     freopen("output.txt","w",stdout);71     n=read();m=read();72     int x,y,z;73     for1(i,n-1)x=read(),y=read(),insert(x,y),insert(y,x);74     memset(dep,-1,sizeof(dep));75     dep[1]=0;76     dfs(1);77     while(m--)78      {79          x=read();y=read();z=read();80          ans=inf;pos=0;81          update(x,y,z);82          update(y,z,x);83          update(z,x,y);84          printf("%d %d\n",pos,ans);85      }86     return 0;87 }