这个世界需要一个英雄来拯救

#include<bits/stdc++.h>
#define LL int
using namespace std;
const LL N=2e5+5;
const LL M=20;
LL T,n,m,x,y,xx,yy,fa[N][M+5],dep[N],vis[N],timA[N][2],timB[N][2];
vector<LL>v[N];
inline int read() {
	char c = getchar();
	int f = 1;
	int sum = 0;
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') {
		f = -1;
		c = getchar();
	}
	do {
		sum = (sum << 3) + (sum << 1) + c - '0';
		c = getchar();
	} while (c >= '0' && c <= '9');
	return sum * f;
}
void dfs(LL x,LL f)
{ 
	fa[x][0]=f,dep[x]=dep[f]+1;
	for(int i=1;i<=M;i++)
	{
		fa[x][i]=fa[fa[x][i-1]][i-1];	
	}
	for(LL i:v[x])
	{
		if(f==i)continue;
		dfs(i,x);
	}
}
LL gcd(LL x,LL y)
{
	if(!y)return x;
	return gcd(y,x%y);
}
void exgcd(LL a,LL b,LL &x,LL &y)
{
	if(!b)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=(a/b)*x;
}
LL lca(LL x,LL y)
{
	while(dep[x]!=dep[y])
	{
		if(dep[x]<dep[y])swap(x,y);
		LL t=log2(dep[x]-dep[y]);
		x=fa[x][t];
	}
	if(x==y)return x;
	for(int i=M;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i],y=fa[y][i];
		}
	}
	return fa[x][0];
}
int main()
{
	T=read();
	while(T--)
	{
		memset(v,0,sizeof(v));
		memset(fa,0,sizeof(fa));
		memset(dep,0,sizeof(dep));
		memset(vis,0,sizeof(vis));
		memset(timA,0,sizeof(timA));
		memset(timB,0,sizeof(timB));
		n=read(),m=read();
		for(int i=1;i<=n-1;i++)
		{
			x=read(),y=read();
			v[x].push_back(y);
			v[y].push_back(x);
		}
		dfs(1,0);
		while(m--)
		{
			x=read(),y=read(),xx=read(),yy=read();
			LL f1=lca(x,y),f2=lca(xx,yy);
			vector<LL>A,B,v1;
			for(int i=x;i!=f1;i=fa[i][0])
			{
				A.push_back(i);
				vis[i]=1;
			}
			A.push_back(f1);
			vis[f1]++;
			for(int i=y;i!=f1;i=fa[i][0])
			{
				v1.push_back(i);
				vis[i]++;
			}
			reverse(v1.begin(),v1.end());
			for(LL i:v1)
			{
				A.push_back(i);
			}
			v1.clear();
			for(int i=xx;i!=f2;i=fa[i][0])
			{
				B.push_back(i);
				vis[i]++;
			}
			B.push_back(f2);
			vis[f2]++;
			for(int i=yy;i!=f2;i=fa[i][0])
			{
				v1.push_back(i);
				vis[i]++;
			}
			reverse(v1.begin(),v1.end());
			for(LL i:v1)
			{
				B.push_back(i);
			}	
			LL lena=A.size(),lenb=B.size();
			for(int i=0;i<lena;i++)
			{
				timA[A[i]][0]=i;
				timA[A[i]][1]=2*(lena-1)-i;
			}
			for(int i=0;i<lenb;i++)
			{
				timB[B[i]][0]=i;
				timB[B[i]][1]=2*(lenb-1)-i;
			}	
			lena--,lenb--;
			lena*=2,lenb*=2;
			LL ans=-1,tim=N*4;
			for(int i=1;i<=n;i++)
			{
				if(vis[i]==2)
				{
					for(int p1=0;p1<=1;p1++)
					{
						for(int p2=0;p2<=1;p2++)
						{
							LL k1,k2,c=timA[i][p1]-timB[i][p2];
							LL d=gcd(-lenb,lena);
							if(c%d!=0)continue;
							exgcd(lena,-lenb,k1,k2);
							k1*=c/d,k2*=c/d;
							k1%=lenb/d;
							if(k1<0)k1+=lenb/d;
							while((k1-lenb/d)*lena>timA[i][p1])k1-=lenb/d;
							LL X=timA[i][p1]+k1*lena;
							if(tim>X)tim=X,ans=i;
						}
					}
				}
			}
			for(LL i:A)vis[i]=0;
			for(LL i:B)vis[i]=0;
			printf("%d\n",ans);
		}
	}
}