安德烈大师非常喜欢树$$$^{\dagger}$$$,所以他有一棵由$$$n$$$顶点组成的树。
但事情没那么简单。蒂莫菲大师决定从树上偷一个顶点。如果 Timofey 从树中窃取了顶点 $$$v$$$,则顶点 $$$v$$$ 以及一端位于顶点 $$$v$$$ 的所有边都会从树中删除,而其他顶点的数量保持不变。为了防止安德烈生气,蒂莫菲决定再次将生成的图变成树。为此,他可以在任意顶点$$$a$$$和$$$b$$$之间添加边,但是添加这样的边时,他必须向大师援助中心支付$$$|a - b|$$$硬币。
请注意,生成的树不包含顶点 $$$v$$$。
Timofey 尚未决定从树中删除哪个顶点 $$$v$$$,因此他想知道对于每个顶点 $$$1 \leq v \leq n$$$,删除顶点 $$$v$$$ 后使图再次成为树所需的最少硬币数,以及需要添加哪些边。
$$$^{\dagger}$$$树是无环的无向连通图。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$5 \le n \le 2\cdot10^5$$$) — Andrey 树中的顶点数。
接下来的 $$$n - 1$$$ 行包含树边缘的描述。这些行的第 $$$i$$$ 包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — 由第 $$$i$$$ 条边连接的顶点数。
保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。
输出
对于每个测试用例,按以下格式输出答案:
对于每个顶点$$$v$$$(按照从$$$1$$$到$$$n$$$的顺序),在第一行输出两个整数$$$w$$$和$$$m$$$——删除顶点$$$v$$$后使图再次成为树所需花费的最小硬币数量,以及添加的边的数量。
然后输出 $$$m$$$ 行,每行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n, a \ne v, b \ne v$$$, $$$a \ne b$$$) — 添加边的末端。
如果有多种添加边的方法,则可以以最小的成本输出任何解决方案。
示例
输入 #1
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
输出 #1
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
注意
在第一个测试用例中:
考虑删除顶点 $$$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$$$:
不需要添加边,因为删除顶点后图仍将是一棵树。