2651 - 城市改建

　　cs城由n座美丽的小镇组成，小镇之间通过n-1条公路连接，任意两个小镇都能互达。尽管如此，居民还是会向他们的负责人yy抱怨：两座小镇之间的距离(经过的公路数)太远了！yy体恤民情，打算重建城市。yy认为，n-1条公路足矣，丝毫没有浪费，他决定依旧保持这个结构。并且，yy并不打算大兴土木，因此他只会拆除一条公路再新建一条公路。 　　作为yy的助理，你需要帮他计算出重建城市后最远的两座小镇距离最近是多少(若存在两个小镇不能互达，则距离为无穷远)，并给出任意一组合法方案。

输入

　　输入的第一行包含一个整数n。接下来n-1行，每行两个整数a、b，代表一条公路。

输出

　　输出3行。第一行包含一个整数，表示重建后最远的两座小镇的最近距离。第二行包含两个整数，代表拆除的公路。第三行包含两个整数，代表新建的公路。

样例

输入

4
1 2
2 3
3 4

样例输出
2
3 4
4 2

输出

数据规模和约定
　　20%的数据满足：n≤30
　　60%的数据满足：n≤3000
　　100%的数据满足：1≤n≤300000、1≤a、b≤n 保证输入数据合法
　　Note：如果输出第一行正确，后两行有误或缺失，你可以得到该测试点40%的分数

提示

如果有人愿意写special judge程序，请留言给lavendir

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题