Somebody once told me...
Shrek has outhouses in his swamp, indexed from to . 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 , , such that there is a road from to both and but no road from to , and replace the road connecting to with a road connecting to .
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 — the number of outhouses in Shrek’s swamp.
The following n-1 lines each contain two integers , detailing that there exists a road connecting outhouses and .
3\leq n\leq 10^3.
It is guaranteed that there always exists a solution using at most 10^6 moves.
In the first line, print a single integer — the smallest number of moves needed to turn Shrek’s swamp into a star.
In the following lines print three integers , and ; denoting that Shrek should preform the described move to outhouses , and .
If several possible sequences of moves exist, you can print any of them.
Example
In the sample case, after the first move, outhouse will be connected by road to outhouses , and , and outhouse will be connected by road to outhouse . After the second move, outhouse 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.