Mole

Time limit1sMemory limit128 MB

Summary

Given a tree, remove one edge and add one edge (keeping it connected) to minimize the tree's diameter, and output the resulting diameter with the edges swapped.

Level: Hard9 of 10
Topics: Tree, Graph, DFS, Greedy
Solved: No attempts yet

Problem

A mole's home is a tree with N rooms and N-1 tunnels. Between any two rooms there is exactly one path, and the distance between two rooms is the number of tunnels on that path.

The mole will close one tunnel and dig one new tunnel. After the reconstruction, all rooms must still be connected. Among all possible reconstructions, minimize the greatest distance between any two rooms.

Given the current tunnels, print the minimum possible greatest distance after reconstruction, the tunnel to close, and the new tunnel to build.

Input

The first line contains the number of rooms N. The rooms are numbered from 1 to N. (3 ≤ N ≤ 300,000)

Each of the next N-1 lines contains two room numbers connected by a tunnel.

Output

On the first line, print the minimum possible greatest distance between two rooms after reconstruction.

On the second line, print the two room numbers connected by the tunnel to close.

On the third line, print the two room numbers connected by the new tunnel.

If there is more than one valid answer, you may print any one of them.

Examples2

Example 1
Input
```
4
1 2
2 3
3 4
```
Expected output
```
2
3 4
4 2
```
Example 2
Input
```
7
1 3
2 3
2 7
4 3
7 5
3 6
```
Expected output
```
3
2 3
7 3
```