← 返回题目列表

Codeforces · 911/F

F. 树木破坏

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

给你一棵有 n 个顶点的未加权树。然后对树应用 n-1 个以下操作。单个操作由以下步骤组成:

1.选择两片叶子;
2. 将它们之间的简单路径的长度添加到答案中;
3. 从树上移除选定的叶子之一。

初始答案(在应用操作之前)是 0。显然,在 n - 1 次这样的操作之后,树将由单个顶点组成。

计算您可以实现的最大可能答案,并构建一系列操作来实现该答案!

输入

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

接下来的 n - 1 行以 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) 的形式描述树的边。保证给定的图是一棵树。

输出

在第一行打印一个整数——最大可能的答案。

在接下来的 n - 1 行中,按照 ai, bi, ci 格式按应用顺序打印操作,其中 ai, bi — 在当前操作中选择的一对叶子 (1 ≤ ai, bi ≤ n),ci (1 ≤ ci ≤ n, ci = ai 或 ci = bi) — 在当前操作中从树中删除的选择叶子。

请参阅示例以更好地理解。

示例

输入 #1

3
1 2
1 3

输出 #1

3
2 3 3
2 1 1

输入 #2

5
1 2
1 3
2 4
2 5

输出 #2

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