给你一棵有 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
注意
这是第二个样本的图片。添加的边缘是黑色的,删除的边缘是虚线的。