# Round #670 Div. 2

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; ++i)
const int N = 100010;
int n, sz[N], fa[N], minn = 1e9, cent1, cent2;
vector<int> g[N];
int S;
void dfs(int x, int f) {
fa[x] = f, sz[x] = 1;
int mx = 0;
for (int y : g[x]) {
if (y == f) continue;
dfs(y, x);
sz[x] += sz[y];
mx = max(mx, sz[y]);
}
mx = max(mx, n - sz[x]);
if (mx < minn)
minn = mx, cent1 = x, cent2 = 0;
else if (mx == minn)
cent2 = x;
}
void dfs2(int x, int f) {
if (g[x].size() == 1) {
S = x;
return;
}
for (int y : g[x]) {
if (y == f) continue;
dfs2(y, x);
}
}
int main() {
int tc;
cin >> tc;
while (tc--) {
cin >> n;
cent1 = cent2 = 0, minn = 1e9;
rep(i, 1, n + 1) g[i].clear(), fa[i] = 0;
rep(i, 1, n) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
if (!cent2) {
printf("1 %d\n1 %d\n", g[1][0], g[1][0]);
continue;
}
if (fa[cent1] != cent2) swap(cent1, cent2);
dfs2(cent1, cent2);
printf("%d %d\n%d %d\n", S, fa[S], S, cent2);
}
}

## 1406D - Three Sequences¶

1. $$b_1 + c_i = a_i$$
2. $$b$$单调不下降
3. $$c$$单调不上升

\begin{cases} \left \{ \begin{aligned} b_i &= b_{i-1}+a_i-a_{i-1} \\ c_i &= c_{i-1} \end{aligned} \right. & \text{if}\quad a_i > a_{i-1} \\ \left \{ \begin{aligned} b_i &= b_{i-1} \\ c_i &= c_{i-1}+a_i-a_{i-1} \end{aligned} \right. & \text{if}\quad a_i < a_{i-1} \\ \end{cases}

$$K = \sum\limits_{i=2}^{n}\max(0,a_i-a_{i-1})$$，设$$c_1 = x$$，则$$b_1 = a_1 - x$$$$b_n = b_1 + K = a_1 - x + K$$