311111: CF1935F. Andrey's Tree

F. Andrey's Treetime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExampleInput

3
5
1 3
1 4
4 5
3 2
5
4 2
4 3
3 5
5 1
5
2 1
1 5
1 4
1 3

Output

1 1
3 4

0 0

1 1
1 2

2 1
3 5

0 0

0 0

0 0

1 1
1 2

1 1
1 2

1 1
1 2

3 3
2 3
4 5
3 4

0 0

0 0

0 0

0 0

Note

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.

题目大意：
Andrey非常喜欢树，他有一棵由n个顶点组成的树。Timofey决定从树中偷走一个顶点v。如果Timofey偷走了顶点v，那么顶点v和所有一端在顶点v的边将从树中被移除，而其他顶点的编号保持不变。为了防止Andrey难过，Timofey决定让结果图再次成为一棵树。为此，他可以在任意顶点a和b之间添加边，但在添加这样的边时，他必须向大师助手中心支付|a - b|枚硬币。
注意，结果树不包含顶点v。
Timofey尚未决定他将从树中移除哪个顶点v，因此他想知道对于每个顶点1≤v≤n，移除顶点v后，使图再次成为树所需花费的最少硬币数，以及需要添加哪些边。

输入数据格式：
每个测试用例包含多个测试。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数n（5≤n≤2*10^5）——Andrey的树的顶点数。
接下来n-1行包含树的边的描述。这些行的第i行包含两个整数u_i和v_i（1≤u_i，v_i≤n）——第i条边连接的顶点编号。
保证给定的边构成一棵树。
保证所有测试用例的n之和不超过2*10^5。

输出数据格式：
对于每个测试用例，按以下格式输出答案：
对于每个顶点v（按从1到n的顺序），在第一行输出两个整数w和m——移除顶点v后，使图再次成为树所需花费的最少硬币数和添加的边数。
然后输出m行，每行包含两个整数a和b（1≤a，b≤n，a≠v，b≠v，a≠b）——添加的边的端点。
如果有多种添加边的方式，你可以输出任何具有最小成本的解决方案。题目大意： Andrey非常喜欢树，他有一棵由n个顶点组成的树。Timofey决定从树中偷走一个顶点v。如果Timofey偷走了顶点v，那么顶点v和所有一端在顶点v的边将从树中被移除，而其他顶点的编号保持不变。为了防止Andrey难过，Timofey决定让结果图再次成为一棵树。为此，他可以在任意顶点a和b之间添加边，但在添加这样的边时，他必须向大师助手中心支付|a - b|枚硬币。 注意，结果树不包含顶点v。 Timofey尚未决定他将从树中移除哪个顶点v，因此他想知道对于每个顶点1≤v≤n，移除顶点v后，使图再次成为树所需花费的最少硬币数，以及需要添加哪些边。 输入数据格式： 每个测试用例包含多个测试。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数n（5≤n≤2*10^5）——Andrey的树的顶点数。 接下来n-1行包含树的边的描述。这些行的第i行包含两个整数u_i和v_i（1≤u_i，v_i≤n）——第i条边连接的顶点编号。 保证给定的边构成一棵树。 保证所有测试用例的n之和不超过2*10^5。 输出数据格式： 对于每个测试用例，按以下格式输出答案： 对于每个顶点v（按从1到n的顺序），在第一行输出两个整数w和m——移除顶点v后，使图再次成为树所需花费的最少硬币数和添加的边数。 然后输出m行，每行包含两个整数a和b（1≤a，b≤n，a≠v，b≠v，a≠b）——添加的边的端点。 如果有多种添加边的方式，你可以输出任何具有最小成本的解决方案。