CF911F.Tree Destruction

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:

1. choose two leaves;
2. add the length of the simple path between them to the answer;
3. 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!

给你一棵包含 $n$ 个顶点的无权树。随后对该树执行 $n-1$ 次操作。每次操作包含以下步骤：

1. 选择两个叶子节点；
2. 将它们之间简单路径的长度加到答案中；
3. 从树中删除所选的两个叶子节点中的一个。

初始答案（执行操作前）为 $0$。显然，经过 $n-1$ 次这样的操作后，树将仅剩一个顶点。

请计算你能得到的最大可能答案，并构造一个能达成该最大答案的操作序列！

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 a__i, b__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i). It is guaranteed that given graph is a tree.

第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$）—— 树中顶点的数量。

接下来的 $n-1$ 行描述树的边，每行格式为 $a_i,\ b_i$（$1 \leq a_i, b_i \leq n$，且 $a_i \neq b_i$）。保证所给图是一棵树。

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 a__i, b__i, c__i, where a__i, b__i — pair of the leaves that are chosen in the current operation (1 ≤ a__i, b__i ≤ n), c__i (1 ≤ c__i ≤ n, c__i = a__i or c__i = b__i) — choosen leaf that is removed from the tree in the current operation.

See the examples for better understanding.

第一行输出一个整数——最大可能的答案。

接下来的 $n-1$ 行按操作执行顺序输出各操作，每行格式为 $a_i,\,b_i,\,c_i$，其中 $a_i,\,b_i$ 是当前操作中所选的一对叶子节点（$1 \leq a_i, b_i \leq n$），$c_i$（$1 \leq c_i \leq n$，且 $c_i = a_i$ 或 $c_i = b_i$）是当前操作中从树中删除的叶子节点。

参见示例以加深理解。