All-Star

Limits: 2 sec., 512 MiB

Somebody once told me...

Shrek has $n$ outhouses in his swamp, indexed from $1$ to $n$. These outhouses are connected by $n-1$ bidirectional roads, such that it is possible to get from any outhouse to any other by a series of roads.

In one move, Shrek may choose three distinct outhouses $x$, $y$, $z$ such that there is a road from $y$ to both $x$ and $z$ but no road from $x$ to $z$, and replace the road connecting $y$ to $z$ with a road connecting $x$ to $z$.

It is well-known that Shrek can only be described as an "all-star", so he wants his swamp to resemble a star. More precisely, he wants to make some number of moves such that there exists an outhouse that is connected to every other one by a road. Help him find a way to do so in the smallest number of moves.

Input

The first line contains a single integer $n$ — the number of outhouses in Shrek’s swamp.

The following $n-1$ lines each contain two integers $u$, $v$ detailing that there exists a road connecting outhouses $u$ and $v$.

Output

In the first line, print a single integer $m$ — the smallest number of moves needed to turn Shrek’s swamp into a star.

In the following $m$ lines print three integers $x$, $y$ and $z$; denoting that Shrek should preform the described move to outhouses $x$, $y$ and $z$.

If several possible sequences of moves exist, you can print any of them.

Constraints

$3\leq n\leq 10^3$.

It is guaranteed that there always exists a solution using at most $10^6$ moves.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 1 2 2 3 3 4 4 5	2 3 2 1 3 4 5

Notes

In the sample case, after the first move, outhouse $3$ will be connected by road to outhouses $1$, $2$ and $4$, and outhouse $5$ will be connected by road to outhouse $4$. After the second move, outhouse $3$ will have roads connecting it to all other outhouses, and so the swamp will be a star. It is impossible to make the swamp a star after just one move, so the above answer is correct.