Moles are tidy and ha\(rd-wo\)rking animals. Our mole likes to keep its underground residence in utmost
order, so that everyone living there knows where to find things.
To achieve this, the mole connected rooms with tunnels so that there is a single unique way to get from
one room to any other room. The distance between two rooms is the number of halls passed on the
way from one to the other.
Despite all the effort, some of the mole's guests are complaining that it takes too long to walk between
certain pairs of rooms.
The mole decided to reconstruct her residence, closing one tunnel and opening a new one, so that the
distance between the farthest two rooms is the smallest possible, but so that it is still possible to
reach every room from every other room.
Write a program which determines the distance between the farthest two rooms after reconstruction,
which tunnel to close and which to open.

The first line contains an integer \(N\) (\(1 \le N \le 300\,000\)), the number of rooms. The rooms are numbered \(1\) to \(N\).

Each of the next \(N-1\) lines contains two integers, the numbers of rooms a tunnel connects.

Output on separate lines, in order:

• The distance between the two farthest rooms after reconstruction.
• A pair of integers representing a previously existing tunnel, which should be closed.
• A pair of integers, the rooms between which a new tunnel should be opened.

Note: The solution will not necessarily be unique. Output any reconstruction plan which achieves the smallest distance between the farthest two rooms.

Scoring: In test cases worth \(40\%\) of points, \(N\) will be less than \(30\). In test cases worth \(70\%\) of points, \(N\) will be less than \(3000\). Additionally, if the first line of your output is correct and the other two are missing or incorrect, you will receive about \(70\%\) of the value of that test case.

riseoj 작성

출처 COCI 2008/2009 Contest 1