CF843C.Upgrading Tree

You are given a tree with n vertices and you are allowed to perform no more than 2_n_ transformations on it. Transformation is defined by three vertices x, y, y' and consists of deleting edge (x, y) and adding edge (x, y'). Transformation x, y, y' could be performed if all the following conditions are satisfied:

1. There is an edge (x, y) in the current tree.
2. After the transformation the graph remains a tree.
3. After the deletion of edge (x, y) the tree would consist of two connected components. Let's denote the set of nodes in the component containing vertex x by V__x, and the set of nodes in the component containing vertex y by V__y. Then condition |V__x| > |V__y| should be satisfied, i.e. the size of the component with x should be strictly larger than the size of the component with y.

You should minimize the sum of squared distances between all pairs of vertices in a tree, which you could get after no more than 2_n_ transformations and output any sequence of transformations leading initial tree to such state.

Note that you don't need to minimize the number of operations. It is necessary to minimize only the sum of the squared distances.

给你一棵包含 $n$ 个顶点的树，你最多可对其执行 $2n$ 次变换。每次变换由三个顶点 $x,\,y,\,y'$ 定义，其操作为：删除边 $(x,\,y)$，并添加边 $(x,\,y')$。变换 $x,\,y,\,y'$ 可以执行当且仅当满足以下全部条件：

1. 当前树中存在边 $(x,\,y)$；
2. 变换后所得图仍为一棵树；
3. 删除边 $(x,\,y)$ 后，树将分裂为两个连通分量。记包含顶点 $x$ 的连通分量中所有节点构成的集合为 $V_x$，包含顶点 $y$ 的连通分量中所有节点构成的集合为 $V_y$。则需满足 $|V_x| > |V_y|$，即含 $x$ 的连通分量的大小严格大于含 $y$ 的连通分量的大小。

你需要在至多 $2n$ 次变换后，使得树中所有顶点对之间的距离的平方和最小，并输出任意一个能将初始树变为该最优状态的变换序列。

注意：你无需最小化操作次数，只需最小化所有顶点对间距离的平方和。

The first line of input contains integer n (1 ≤ n ≤ 2·105) — number of vertices in tree.

The next n - 1 lines of input contains integers a and b (1 ≤ a, b ≤ n, a ≠ b) — the descriptions of edges. It is guaranteed that the given edges form a tree.

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

接下来的 $n-1$ 行每行包含两个整数 $a$ 和 $b$（$1 \leq a, b \leq n$，且 $a \neq b$）——边的描述。保证所给的边构成一棵树。

In the first line output integer k (0 ≤ k ≤ 2_n_) — the number of transformations from your example, minimizing sum of squared distances between all pairs of vertices.

In each of the next k lines output three integers x, y, y' — indices of vertices from the corresponding transformation.

Transformations with y = y' are allowed (even though they don't change tree) if transformation conditions are satisfied.

If there are several possible answers, print any of them.

第一行输出一个整数 $k$（$0 \leq k \leq 2n$）—— 表示你所给出的例子中变换的次数，该次数需使得所有顶点对之间的平方距离之和最小。

接下来的 $k$ 行中，每行输出三个整数 $x,\,y,\,y'$ —— 分别表示对应变换中的顶点编号。

允许 $y = y'$ 的变换（尽管此类变换不改变树的结构），只要其满足变换条件即可。

若存在多个可能的答案，输出任意一个即可。

This is a picture for the second sample. Added edges are dark, deleted edges are dotted.

这是第二个样例的示意图。新增的边为实线（深色），删除的边为虚线。