题目描述

有一棵 $n$ 个点的树，边权都为 $1$。

现在想删去一条边，增加一条边，使得最远的两个点距离最短。

输入格式

第一行为一个整数 $n$。

接下来 $n-1$ 行，每行两个整数 $a$ 和 $b$，表示有树上有一条从 $a$ 到 $b$ 的无向边。

输出格式

本题存在 SPJ。

第一行只有一个整数，表示删去一条边，增加一条边后最远的两个点的距离。

第二行两个整数，表示被删掉的一条边。

第三行两个整数，表示被增加的一条边。

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 

提示

数据规模与约定

• 对于 $40\%$ 的数据，保证 $n\le 30$。
• 对于 $70\%$ 的数据，保证 $n\le 3\times 10^3$。
• 对于 $100\%$ 的数据，保证 $1\le n \le 3\times 10^5$，$1\le a,b\le n$。

计分标准

• 如果输出的第一行不正确，得 $0$ 分。
• 如果输出得第一行正确，但是剩下的数字不正确或数量不足四个，得对应测试点 $70\%$ 的分数。
• 如果输出第一行正确，且给出的方案是可行且正确的，得到对应测试点 $100\%$ 的分数。

说明

本题译自 Croatian Open Competition in Informatics 2008/2009 Contest #1 T6 KRTICA。

SPJ provided by @Tweetuzki