[POI2015] MOD

题目描述

给定一棵无根树，边权都是 $1$，请去掉一条边并加上一条新边，定义直径为最远的两个点的距离，请输出所有可能的新树的直径的最小值和最大值

输入格式

第一行包含一个正整数 $n$，表示这棵树的点数。
接下来 $n-1$ 行，每行包含两个正整数，表示 $u,v$ 之间有一条边。

输出格式

第一行输出五个正整数 $k,x_1,y_1,x_2,y_2$，其中 $k$表示新树直径的最小值，$x_1,y_1$ 表示这种情况下要去掉的边的两端点，$x_2,y_2$ 表示这种情况下要加上的边的两端点。

第二行输出五个正整数 $k,x_1,y_1,x_2,y_2$，其中 $k$ 表示新树直径的最大值，$x_1,y_1$ 表示这种情况下要去掉的边的两端点，$x_2,y_2$ 表示这种情况下要加上的边的两端点。若有多组最优解，输出任意一组。

样例 #1

样例输入 #1

6
1 2
2 3
2 4
4 5
6 5

样例输出 #1

3 4 2 2 5
5 2 1 1 6

提示

【数据范围】

对于 $100\%$ 的数据，$1\le n \le 5\times 10^5$。

原题名称：Modernizacja autostrady。

感谢 @cn：苏卿念 提供 spj