← 返回题目列表

Codeforces · 843/C

C. 升级树

中文机器翻译题面 查看原题

给你一棵有 n 个顶点的树,并且允许你对其执行不超过 2n 次变换。变换由三个顶点 x、y、y' 定义,包括删除边 (x, y) 和添加边 (x, y')。如果满足以下所有条件,则可以执行变换 x, y, y':

1. 当前树中有一条边 (x, y)。
2. 转换后,图仍然是树。
3. 删除边 (x, y) 后,树将由两个连接的组件组成。让我们用 Vx 表示包含顶点 x 的组件中的节点集合,用 Vy 表示包含顶点 y 的组件中的节点集合。然后条件|Vx| > |Vy|应满足,即 x 分量的大小应严格大于 y 分量的大小。

您应该最小化树中所有顶点对之间的平方距离之和,您可以在不超过 2n 次变换后获得该距离,并输出导致初始树达到这种状态的任何变换序列。

请注意,您不需要最小化操作数量。有必要仅最小化距离平方和。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 2·105) — 树中的顶点数。

接下来的 n - 1 行输入包含整数 a 和 b (1 ≤ a, b ≤ n, a ≠ b) — 边的描述。保证给定的边形成一棵树。

输出

在第一行中输出整数 k (0 ≤ k ≤ 2n) — 示例中的变换数量,最小化所有顶点对之间距离的平方和。

在接下来的 k 行中,每一行输出三个整数 x、y、y' — 来自相应变换的顶点索引。

如果满足转换条件,则允许 y = y' 进行转换(即使它们不会更改树)。

如果有多个可能的答案,请打印其中任何一个。

示例

输入 #1

3
3 2
1 3

输出 #1

0

输入 #2

7
1 2
2 3
3 4
4 5
5 6
6 7

输出 #2

2
4 3 2
4 5 6

注意

这是第二个样本的图片。添加的边缘是黑色的,删除的边缘是虚线的。