题意翻译

给定一棵节点数为 $n$ 的树，请你在树上删一条边然后加上一条边，使得该树的重心唯一。（删掉的边和加上的边可以是同一条）

输入格式

第 $1$ 行一个正整数 $T$ ，表示有 $T$ 组测试数据。

对于每组测试数据，第 $1$ 行一个正整数 $n$ ，表示该树有 $n$ 个节点

第 $2$ 行到第 $n$ 行每行两个正整数 $x,y$，表示 $x$ 到 $y$ 有一条无向边。

输出格式

对于每一组测试数据。

第 $1$ 行两个正整数 $x_1,y_1$ ，表示删的边的端点为 $x_1,y_1$。

第 $2$ 行两个正整数 $x_2,y_2$ ，表示连的边的端点为 $x_2,y_2$。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

数据范围和约定

对于 $100\%$ 的数据，满足 $1 \leq \sum n \leq 10^5$。

分析

树的重心的简单应用题。

做法

第一遍 $\text{dfs}$ 找出树的重心，若只有一个重心的话就直接随便删一条边然后加上即可。

否则的话，则两个重心必然相邻（否则取这两个重心路径上的中点作为重心更优）。我们钦定其中一个为根节点，那么另一个一定是其子节点。

之后在不是根节点的重心上随便删掉一个通往子节点的边，并将其与根节点链接即可。

证明

那么为什么这是对的呐？

显然，被钦定为根的节点操作之后依然是重心，而未被钦定的那个因为删去了一个子节点，其最大子树大小变大，显然不再是重心了。

由于以上操作只是这三个点之间的操作，与另外的节点没有关系。因此另外的节点也不会是重心。

综上，命题得证。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 998244353;

int n;

struct Edge{
    int from , to , last;
}edge[M << 1];

int edge_num;
int head[M << 1];

I void add_edge(int from , int to){
    edge[++ edge_num] = (Edge){from , to , head[from]}; head[from] = edge_num;
    edge[++ edge_num] = (Edge){to , from , head[to]}; head[to] = edge_num;
}

int fa[M] , size[M] , cnt = 0x3f3f3f3f; 

int root[3];

void dfs1(int x , int f){
    fa[x] = f;
    size[x] = 1;
    int sz = 0;
    PE(i , x){
        int to = edge[i].to;
        if(to == f) continue;
        dfs1(to , x);
        size[x] += size[to];
        sz = max(sz , size[to]);
    }
    sz = max(sz , n - size[x]);
    if(sz < cnt){
        cnt = sz; root[1] = x , root[2] = 0;
    }
    else if(sz == cnt){
        root[2] = x;
    }
}

int leaf;

void dfs2(int x , int f){
    if(size[x] == 1){
        leaf = x;
        return;
    }
    PE(i , x){
        int to = edge[i].to;
        if(to == f) continue;
        dfs2(to , x);
    }
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    int t; read(t);
    while(t --){
        edge_num = 0;
        rep(i , 1 , n){
            head[i] = fa[i] = size[i] = 0;
        }
        cnt = 0x3f3f3f3f;
        root[1] = root[2] = 0;
        
        read(n);
        rep(i , 1 , n - 1){
            int u , v;
            read(u) , read(v);
            add_edge(u , v);
        }
        dfs1(1 , 0);
        if(root[1] != 0 && root[2] == 0){
            printf("%d %d\n%d %d\n" , edge[1].from , edge[1].to , edge[1].to , edge[1].from);
            continue;
        }
        if(fa[root[1]] != root[2]) swap(root[1] , root[2]);
        dfs2(root[1] , root[2]);
        printf("%d %d\n%d %d\n" , leaf , fa[leaf] , leaf , root[2]);
    }

    return 0;
}