CF2107D

#include<bits/stdc++.h>
using namespace std;
const int N=150005;
struct G
{
	int ne,to;
}e[2*N];
struct T
{
	int d,x,y;
}ans[N];
int he[N],idx,a[N],f[N],u[N],v[N],c[N],top,sz,fat[N],vis[N],g[N],mxid[N];
void add(int x,int y)//加边
{
	e[++idx].ne=he[x];
	e[idx].to=y;
	he[x]=idx;
}
void dfs(int x,int fa)//树形dp
{
	fat[x]=fa;//记录祖先
	c[++top]=x;//块内元素
	f[x]=0;//最长路径长度
	g[x]=0;//最长的以当前根为起点的路径长度
	mxid[x]=x;//能取到g[x]的另一个端点的id最大值
	int mx=0,cmx=0,id=x,cid=x;//最长的以当前根为起点的路径长度、次最长的以当前根为起点的路径长度、能取到mx的另一个端点的id最大值、能取到cmx的另一个端点的id最大值
	for(int i=he[x];i;i=e[i].ne)//先取最长路径
	{
		int y=e[i].to;
		if(a[y]||y==fa)continue;
		dfs(y,x);
		if(g[y]>mx||(g[y]==mx&&mxid[y]>mxid[id]))
		{
			mx=g[y];
			id=y;
		}
	}
	for(int i=he[x];i;i=e[i].ne)//再取次长路径
	{
		int y=e[i].to;
		if(a[y]||y==fa||y==id)continue;
		if(g[y]>cmx||(g[y]==cmx&&mxid[y]>mxid[cid]))
		{
			cmx=g[y];
			cid=y;
		}
	}
	f[x]=mx+cmx+1;
	g[x]=mx+1;
	u[x]=max(mxid[id],mxid[cid]);//具体构造方案(f[x],u[x],v[x])
	v[x]=min(mxid[id],mxid[cid]);
	mxid[x]=mxid[id];
}
int get(int x)//得到当前联通块答案
{
	top=0;
	dfs(x,0);
	int mx=0,id=x;
	for(int i=1;i<=top;i++)//保证复杂度
	{
		int y=c[i];
		if(f[y]>mx||(f[y]==mx&&(u[y]>u[id]||(u[y]==u[id]&&v[y]>v[id]))))
		{
			id=y;
			mx=f[y];
		}
	}
	return id;
}
void run(int x)//分治，处理路径
{
	x=get(x);
	for(int i=1;i<=top;i++)vis[c[i]]=0;
	ans[++sz]={f[x],u[x],v[x]};
	int s=u[x],t=v[x],lca;//计算lca
	while(s)
	{
		vis[s]=1;
		s=fat[s];
	}
	while(t)
	{
		if(vis[t])
		{
			lca=t;
			break;
		}
		t=fat[t];
	}
	s=u[x];t=v[x];a[lca]=1;//删除路径
	while(s!=lca)
	{
		a[s]=1;
		s=fat[s];
	}
	while(t!=lca)
	{
		a[t]=1;
		t=fat[t];
	}
	s=u[x];t=v[x];//分治
	int lst=0;
	while(lst!=lca)
	{
		for(int i=he[s];i;i=e[i].ne)
		{
			int y=e[i].to;
			if(a[y])continue;
			run(y);
		}
		lst=s;
		s=fat[s];
	}
	while(t!=lca)
	{
		for(int i=he[t];i;i=e[i].ne)
		{
			int y=e[i].to;
			if(a[y])continue;
			run(y);
		}
		t=fat[t];
	}
}
bool cmp(T a,T b)//对每个联通块答案排序
{
	if(a.d!=b.d)return a.d>b.d;
	if(a.x!=b.x)return a.x>b.x;
	return a.y>b.y;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			he[i]=0;
			a[i]=0;
		}
		idx=0;
		for(int i=1;i<n;i++)
		{
			int x,y;
			cin>>x>>y;
			add(x,y);
			add(y,x);
		}
		sz=0;
		run(1);
		sort(ans+1,ans+sz+1,cmp);
		for(int i=1;i<=sz;i++)cout<<ans[i].d<<' '<<ans[i].x<<' '<<ans[i].y<<' ';
		cout<<'\n';
	}
	return 0;
}