CF1935F.Andrey's Tree

Master Andrey loves trees$^{\dagger}$ very much, so he has a tree consisting of $n$ vertices.

But it's not that simple. Master Timofey decided to steal one vertex from the tree. If Timofey stole vertex $v$ from the tree, then vertex $v$ and all edges with one end at vertex $v$ are removed from the tree, while the numbers of other vertices remain unchanged. To prevent Andrey from getting upset, Timofey decided to make the resulting graph a tree again. To do this, he can add edges between any vertices $a$ and $b$, but when adding such an edge, he must pay $|a - b|$ coins to the Master's Assistance Center.

Note that the resulting tree does not contain vertex $v$.

Timofey has not yet decided which vertex $v$ he will remove from the tree, so he wants to know for each vertex $1 \leq v \leq n$, the minimum number of coins needed to be spent to make the graph a tree again after removing vertex $v$, as well as which edges need to be added.

$^{\dagger}$A tree is an undirected connected graph without cycles.

大师安德烈非常喜爱树$^{\dagger}$，因此他拥有一棵由 $n$ 个顶点构成的树。

但事情并非如此简单。大师季莫费决定从这棵树中偷走一个顶点。若季莫费偷走了顶点 $v$，则顶点 $v$ 及所有以 $v$ 为一个端点的边均被从树中移除，其余顶点的编号保持不变。为避免安德烈生气，季莫费决定使剩余图再次成为一棵树。为此，他可以在任意两个顶点 $a$ 和 $b$ 之间添加边；但每次添加这样一条边时，他必须向大师援助中心支付 $|a - b|$ 枚金币。

注意：最终得到的树不包含顶点 $v$。

季莫费尚未决定将从树中移除哪一个顶点 $v$，因此他希望对每个顶点 $1 \leq v \leq n$，均求出在移除顶点 $v$ 后，使图重新变为一棵树所需花费的最少金币数，以及需要添加的具体边。

$^{\dagger}$ 树是指无向、连通且无环的图。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($5 \le n \le 2\cdot10^5$) — the number of vertices in Andrey's tree.

The next $n - 1$ lines contain a description of the tree's edges. The $i$-th of these lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) — the numbers of vertices connected by the $i$-th edge.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

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

每个测试用例的第一行包含一个整数 $n$（$5 \le n \le 2\cdot10^5$），表示安德烈的树中顶点的数量。

接下来的 $n - 1$ 行描述了树的边。其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$），表示第 $i$ 条边所连接的两个顶点的编号。

保证所给的边构成一棵树。

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

For each test case, output the answer in the following format:

For each vertex $v$ (in the order from $1$ to $n$), in the first line output two integers $w$ and $m$ — the minimum number of coins that need to be spent to make the graph a tree again after removing vertex $v$, and the number of added edges.

Then output $m$ lines, each containing two integers $a$ and $b$ ($1 \le a, b \le n, a \ne v, b \ne v$, $a \ne b$) — the ends of the added edge.

If there are multiple ways to add edges, you can output any solution with the minimum cost.

对于每个测试用例，按如下格式输出答案：

对每个顶点 $v$（按编号从 $1$ 到 $n$ 的顺序），在第一行输出两个整数 $w$ 和 $m$ —— 分别表示删除顶点 $v$ 后，使图重新成为一棵树所需花费的最少硬币数，以及需添加的边数。

随后输出 $m$ 行，每行包含两个整数 $a$ 和 $b$（$1 \le a, b \le n$，$a \ne v$，$b \ne v$，且 $a \ne b$）—— 表示所添加边的两个端点。

若存在多种添加边的方式，可输出任意一种最小代价的方案。

In the first test case:

Consider the removal of vertex $4$:

The optimal solution would be to add an edge from vertex $5$ to vertex $3$. Then we will spend $|5 - 3| = 2$ coins.

In the third test case:

Consider the removal of vertex $1$:

The optimal solution would be:

• Add an edge from vertex $2$ to vertex $3$, spending $|2 - 3| = 1$ coin.
• Add an edge from vertex $3$ to vertex $4$, spending $|3 - 4| = 1$ coin.
• Add an edge from vertex $4$ to vertex $5$, spending $|4 - 5| = 1$ coin.

Then we will spend a total of $1 + 1 + 1 = 3$ coins.

Consider the removal of vertex $2$:

No edges need to be added, as the graph will remain a tree after removing the vertex.

在第一个测试用例中：

考虑移除顶点 $4$：

最优方案是添加一条从顶点 $5$ 到顶点 $3$ 的边，花费 $|5 - 3| = 2$ 枚金币。

在第三个测试用例中：

考虑移除顶点 $1$：

最优方案为：

• 添加一条从顶点 $2$ 到顶点 $3$ 的边，花费 $|2 - 3| = 1$ 枚金币；
• 添加一条从顶点 $3$ 到顶点 $4$ 的边，花费 $|3 - 4| = 1$ 枚金币；
• 添加一条从顶点 $4$ 到顶点 $5$ 的边，花费 $|4 - 5| = 1$ 枚金币。

此时总共花费 $1 + 1 + 1 = 3$ 枚金币。

考虑移除顶点 $2$：

无需添加任何边，因为移除该顶点后图仍保持为一棵树。