暂无SPJ。

题目描述

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\le 30$。

对于 $60\%$ 的数据满足：$n\le 3\times 10^3$。

对于 $100\%$ 的数据满足：$1\le n\le 3\times 10^5,1\le a,b\le n$ 保证输入数据合法。

提示

如果输出第一行正确，后两行有误或缺失，你可以得到该测试点 $40\%$ 的分数。