#include <map>#include <queue>#include <math.h>#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;#define N 500010int head[N];int edgeNum;struct Edge{ int v,to;}edge[N];int edge_u_v[N][2];void addedge(int a,int b){ edge[edgeNum].v = b; edge[edgeNum].to = head[a]; head[a] = edgeNum ++;}int vis[N],depth,ind;int t_vis[N],father[N];int stack[N];void bfs(int u){ vis[u] = 1; queue<int>que; que.push(u); while(!que.empty()){ int tmp = que.front(); que.pop(); if(vis[tmp] >= depth){ depth = vis[tmp]; ind = tmp; } for(int i = head[tmp];i != -1;i = edge[i].to){ int v = edge[i].v; if(vis[v] == 0){ vis[v] = vis[tmp] + 1; father[v] = tmp; que.push(v); } } } int tmp = ind; for(int i = 0;i < depth;i ++){ stack[i] = tmp; tmp = father[tmp]; } return ;}void init(int n){ edgeNum = 0; for(int i = 0;i <= n;i ++) { head[i] = -1; vis[i] = 0; father[i] = -1; }}int main(){ int t; int n; int u,v; scanf("%d",&t); while(t --){ scanf("%d",&n); init(n); for(int i = 0;i < n - 1;i ++){ scanf("%d%d",&u,&v); edge_u_v[i][0] = u; edge_u_v[i][1] = v; addedge(u,v); addedge(v,u); } depth = 1; bfs(1); for(int i = 0;i <= n;i ++) vis[i] = 0; bfs(ind); int ans_one,ans_two; int depth_one,depth_two; init(n); u = stack[depth / 2 - 1]; v = stack[depth / 2]; for(int i = 0;i < n - 1;i ++){ if((edge_u_v[i][0] == u && edge_u_v[i][1] == v) || (edge_u_v[i][1] == u && edge_u_v[i][0] == v)) ; else{ addedge(edge_u_v[i][0],edge_u_v[i][1]); addedge(edge_u_v[i][1],edge_u_v[i][0]); } } int seperation = stack[depth / 2]; int seperation1 = stack[(depth - 1) / 2]; int long_depth = depth; depth = 1; bfs(seperation); for(int i = 0;i <= n;i ++) t_vis[i] = vis[i]; for(int i = 0;i <= n;i ++) vis[i] = 0; bfs(ind); ans_one = stack[depth/2]; depth_one = depth; if(long_depth&1){ addedge(u,v); addedge(v,u); t_vis[seperation] = 0; }else{ seperation = seperation1; } depth = 1; for(int i = 0;i <= n;i ++) vis[i] = t_vis[i]; bfs(seperation); for(int i = 0;i <= n;i ++) vis[i] = t_vis[i]; bfs(ind); if(depth & 1) ans_two = stack[depth/2]; else ans_two = stack[(depth-1)/2]; depth_two = depth; if(ans_one == ans_two){ printf("%d %d %dn",long_depth/2,ans_one,(ans_one == 1)?2:1); }else{ printf("%d %d %dn",max(depth_one/2,depth_two/2),ans_one,ans_two); } } return 0;}
