Somebody once told me...

Shrek 在他的沼泽里有 $n$ 个厕所，编号从 $1$ 到 $n$。这些厕所通过 $n-1$ 条双向道路连接，使得从任何一个厕所出发都能通过一系列道路到达其他任何一个厕所。

在一次移动中，Shrek 可以选择三个不同的厕所 $x, y, z$，使得存在一条从 $y$ 到 $x$ 的道路和一条从 $y$ 到 $z$ 的道路，但不存在从 $x$ 到 $z$ 的道路。他可以将连接 $y$ 和 $z$ 的道路替换为连接 $x$ 和 $z$ 的道路。

众所周知，Shrek 只能被称为“全明星”，所以他希望他的沼泽看起来像一颗星。更准确地说，他希望通过若干次移动，使得存在一个厕所，它与所有其他厕所都通过道路直接相连。请帮助他找到一种以最少移动次数实现这一目标的方法。

输入

第一行包含一个整数 $n$ —— Shrek 沼泽中厕所的数量。

接下来的 $n-1$ 行，每行包含两个整数 $u, v$，表示厕所 $u$ 和 $v$ 之间存在一条道路。

数据范围

$3 \le n \le 10^3$。

保证一定存在一种移动次数不超过 $10^6$ 的解。

输出

第一行输出一个整数 $m$ —— 将 Shrek 的沼泽变成星形所需的最少移动次数。

接下来的 $m$ 行，每行输出三个整数 $x, y, z$，表示 Shrek 应该对厕所 $x, y, z$ 执行上述移动。

如果存在多种可能的移动序列，你可以输出其中任意一种。

样例

输入格式 1

5
1 2
2 3
3 4
4 5

输出格式 1

2
3 2 1
3 4 5

说明

在样例中，第一次移动后，厕所 $3$ 将与厕所 $1, 2, 4$ 相连，厕所 $5$ 将与厕所 $4$ 相连。第二次移动后，厕所 $3$ 将与所有其他厕所相连，沼泽将变成星形。仅通过一次移动是不可能使沼泽变成星形的，因此上述答案是正确的。