All-Star#12970

All-Star

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.

Input

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.

Output

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.

Examples

Example

Loading
Loading

Note

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.