Description

There is a tree with $n$ nodes, and all edge weights are $1$.

Now you want to delete one edge and add one edge, so that the distance between the two farthest nodes is as small as possible.

Input Format

The first line contains an integer $n$.

The next $n-1$ lines each contain two integers $a$ and $b$, indicating that there is an undirected edge from $a$ to $b$ in the tree.

Output Format

This problem uses an SPJ.

The first line contains a single integer, which is the distance between the two farthest nodes after deleting one edge and adding one edge.

The second line contains two integers, indicating the edge that is deleted.

The third line contains two integers, indicating the edge that is added.

4
1 2
2 3
3 4 

2
3 4
4 2 

7
1 3
2 3
2 7
4 3
7 5
3 6 

3
2 3
7 3 

Hint

Constraints

• For $40\%$ of the testdata, $n \le 30$ is guaranteed.
• For $70\%$ of the testdata, $n \le 3 \times 10^3$ is guaranteed.
• For $100\%$ of the testdata, $1 \le n \le 3 \times 10^5$, and $1 \le a, b \le n$.

Scoring

• If the first line of the output is incorrect, you get $0$ points.
• If the first line of the output is correct, but the remaining numbers are incorrect or fewer than four numbers are printed in total, you get $70\%$ of the score for the corresponding test point.
• If the first line of the output is correct, and the given solution is feasible and correct, you get $100\%$ of the score for the corresponding test point.

Notes

This problem is translated from T6 KRTICA of Croatian Open Competition in Informatics 2008/2009, Contest #1.

SPJ provided by @Tweetuzki.

Translated by ChatGPT 5