Description

You are given an unrooted tree with all edge weights equal to $1$. Remove one edge and add one new edge. The diameter is defined as the distance between the farthest pair of nodes. Among all possible new trees obtained this way, output the minimum and the maximum possible diameter.

Input Format

The first line contains a positive integer $n$, the number of nodes in the tree.
The next $n-1$ lines each contain two positive integers, indicating that there is an edge between $u$ and $v$.

Output Format

On the first line, output five positive integers $k, x_1, y_1, x_2, y_2$, where $k$ is the minimum possible diameter of the new tree, $(x_1, y_1)$ are the endpoints of the edge to remove in this case, and $(x_2, y_2)$ are the endpoints of the edge to add in this case.

On the second line, output five positive integers $k, x_1, y_1, x_2, y_2$, where $k$ is the maximum possible diameter of the new tree, $(x_1, y_1)$ are the endpoints of the edge to remove in this case, and $(x_2, y_2)$ are the endpoints of the edge to add in this case. If there are multiple optimal solutions, output any one of them.

6
1 2
2 3
2 4
4 5
6 5

3 4 2 2 5
5 2 1 1 6

Hint

Constraints

For $100\%$ of the testdata, $2 \le n \le 5 \times 10^5$.

Original title: Modernizacja autostrady.

Thanks to @cn：苏卿念 for providing the spj.

Translated by ChatGPT 5