给你一棵有 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