All-Star

Обмеження: 2 сек., 512 МіБ

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.

Вхідні дані

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\).

Вихідні дані

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.

Обмеження

\(3\leq n\leq 10^3\).

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 1 2 2 3 3 4 4 5	2 3 2 1 3 4 5

Примітки

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.