CF1406C.Link Cut Centroids

Fishing Prince loves trees, and he especially loves trees with only one centroid. The tree is a connected graph without cycles.

A vertex is a centroid of a tree only when you cut this vertex (remove it and remove all edges from this vertex), the size of the largest connected component of the remaining graph is the smallest possible.

For example, the centroid of the following tree is $2$, because when you cut it, the size of the largest connected component of the remaining graph is $2$ and it can't be smaller.

However, in some trees, there might be more than one centroid, for example:

Both vertex $1$ and vertex $2$ are centroids because the size of the largest connected component is $3$ after cutting each of them.

Now Fishing Prince has a tree. He should cut one edge of the tree (it means to remove the edge). After that, he should add one edge. The resulting graph after these two operations should be a tree. He can add the edge that he cut.

He wants the centroid of the resulting tree to be unique. Help him and find any possible way to make the operations. It can be proved, that at least one such way always exists.

钓鱼王子热爱树，尤其钟爱仅有一个重心的树。树是一种无环的连通图。

一个顶点是树的重心，当且仅当删除该顶点（同时移除所有与之相连的边）后，剩余图中最大连通分量的大小达到所有可能删除顶点方案中的最小值。

例如，下图所示树的重心是 $2$，因为删去它之后，剩余图中最大连通分量的大小为 $2$，且无法变得更小。

然而，在某些树中，可能存在多个重心，例如：

顶点 $1$ 和顶点 $2$ 均为重心，因为分别删去它们后，剩余图中最大连通分量的大小均为 $3$。

现在钓鱼王子有一棵给定的树。他需要执行以下两步操作：首先，删去树中的一条边；然后，添加一条新边。经过这两步操作后，所得图必须仍是一棵树（即保持无环且连通）。他可以重新添加刚才被删去的那条边。

他希望最终得到的树具有唯一的重心。请帮助他找到任意一种满足条件的操作方案。可以证明，这样的方案至少存在一种。

The input consists of multiple test cases. The first line contains an integer $t$ ($1\leq t\leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($3\leq n\leq 10^5$) — the number of vertices.

Each of the next $n-1$ lines contains two integers $x, y$ ($1\leq x,y\leq n$). It means, that there exists an edge connecting vertices $x$ and $y$.

It's guaranteed that the given graph is a tree.

It's guaranteed that the sum of $n$ for all test cases does not exceed $10^5$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1\leq t\leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3\leq n\leq 10^5$），表示顶点的数量。

接下来的 $n-1$ 行中，每行包含两个整数 $x, y$（$1\leq x,y\leq n$），表示存在一条连接顶点 $x$ 和 $y$ 的边。

保证给定的图是一棵树。

保证所有测试用例的 $n$ 值之和不超过 $10^5$。

For each test case, print two lines.

In the first line print two integers $x_1, y_1$ ($1 \leq x_1, y_1 \leq n$), which means you cut the edge between vertices $x_1$ and $y_1$. There should exist edge connecting vertices $x_1$ and $y_1$.

In the second line print two integers $x_2, y_2$ ($1 \leq x_2, y_2 \leq n$), which means you add the edge between vertices $x_2$ and $y_2$.

The graph after these two operations should be a tree.

If there are multiple solutions you can print any.

对于每个测试用例，输出两行。

第一行输出两个整数 $x_1, y_1$（$1 \leq x_1, y_1 \leq n$），表示你切断顶点 $x_1$ 与 $y_1$ 之间的边。顶点 $x_1$ 与 $y_1$ 之间必须存在边。

第二行输出两个整数 $x_2, y_2$（$1 \leq x_2, y_2 \leq n$），表示你在顶点 $x_2$ 与 $y_2$ 之间添加一条边。

经过上述两次操作后，所得图应是一棵树。

若存在多种解法，输出任意一种即可。

Note that you can add the same edge that you cut.

In the first test case, after cutting and adding the same edge, the vertex $2$ is still the only centroid.

In the second test case, the vertex $2$ becomes the only centroid after cutting the edge between vertices $1$ and $3$ and adding the edge between vertices $2$ and $3$.

注意，你可以添加一条与你切断的边相同的边。

在第一个测试用例中，切断并重新添加同一条边后，顶点 $2$ 仍然是唯一的重心。

在第二个测试用例中，切断顶点 $1$ 与顶点 $3$ 之间的边，并添加顶点 $2$ 与顶点 $3$ 之间的边后，顶点 $2$ 成为唯一的重心。