You are given an unweighted tree with n vertices. Then n−1 following operations are applied to the tree. A single operation consists of the following steps:
choose two leaves;
add the length of the simple path between them to the answer;
remove one of the chosen leaves from the tree.
Initial answer (before applying operations) is 0. Obviously after n−1 such operations the tree will consist of a single vertex.
Calculate the maximal possible answer you can achieve, and construct a sequence of operations that allows you to achieve this answer!
Input
The first line contains one integer number n (2≤n≤2⋅105) — the number of vertices in the tree.
Next n−1 lines describe the edges of the tree in form ai, bi (1≤ai,bi≤n;ai=bi). It is guaranteed that given graph is a tree.
Output
In the first line print one integer number — maximal possible answer.
In the next n−1 lines print the operations in order of their applying in format ai,bi,ci, where ai,bi — pair of the leaves that are chosen in the current operation (1≤ai,bi≤n), ci (1≤ci≤n,ci=ai∨ci=bi) — choosen leaf that is removed from the tree in the current operation.
See the examples for better understanding.
Examples
Input #1
1 2 3
3 1 2 1 3
Output #2
1 2 3
3 2 33 2 11
Input #2
1 2 3 4 5
5 1 2 1 3 2 4 2 5
Output #2
1 2 3 4 5
9 3 55 4 33 4 11 4 22
2. 题解
分析
这道题主要考察的就是求树的直径。树有一个重要的性质:假设结点 s 和 t 之间唯一的简单路径是树的直径,则树中任意结点的最远结点要么是 s 要么是 t 。 于是,对于这道题而言,一定是先删除非树的直径上的所有结点,然后再删除树的直径上的结点。删除非树的直径上的结点先从叶结点开始,即度为 1 的结点,可以用一个队列维护,然后删除后更新父结点的度,一旦父结点变为叶结点(即度为 1 ),则将父结点加入队列中。该题的解答步骤为:
首先以任意结点 u 为根对树进行第一遍 DFS,求出树的直径的某一端点 s 。
然后以 s 为根对树进行第二遍 DFS,求出树的直径的另一端点 t,同时记录所有结点到 s 的简单路径长度。
接着以 t 为根对树进行第三遍 DFS,记录所有结点到 t 的简单路径,同时记录树的直径路径。
然后使用队列维护除 s 和 t 外的所有叶结点,逐一删除队列中的叶结点,并更新父结点的度和队列。对于每个非树的直径上的结点而言,其对答案贡献最大的值即为其到 s 的简单路径长度与到 t 的简单路径长度二者之中的最大值。