鼹鼠是整洁且勤劳的动物。我们的鼹鼠喜欢让它的地下住所保持极度整洁，以便居住在那里的每个人都知道在哪里可以找到东西。

为了实现这一目标，鼹鼠用通道连接了各个房间，使得从任意一个房间到另一个房间有且仅有一条唯一的路径。两个房间之间的距离是它们之间路径上经过的通道数量。

尽管付出了诸多努力，鼹鼠的一些客人仍然抱怨在某些房间之间行走需要花费太长时间。

鼹鼠决定重建她的住所：关闭一条通道并新建一条通道，使得重建后最远两个房间之间的距离尽可能小，同时仍然保证所有房间之间都是连通的（即重建后仍为一棵树）。

编写一个程序，确定重建后最远两个房间之间的距离，以及应该关闭哪条通道、新建哪条通道。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 300\,000$)，表示房间的数量。房间编号为 $1$ 到 $N$。

接下来的 $N-1$ 行，每行包含两个整数，表示一条通道连接的两个房间的编号。

输出格式

依次在独立的行中输出：

• 重建后最远两个房间之间的距离。
• 两个整数，表示一条原本存在的、应该被关闭的通道（连接的两个房间编号）。
• 两个整数，表示应该在其间新建通道的两个房间编号。

注意：解不唯一。输出任何一种能使重建后最远两个房间之间距离最小的重建方案即可。

子任务

• 在占总分 40% 的测试数据中，$N < 30$。
• 在占总分 70% 的测试数据中，$N < 3000$。

此外，如果你的输出中第一行是正确的，而另外两行缺失或错误，你将获得该测试点约 70% 的分数。

样例

输入样例 1

4
1 2
2 3
3 4

输出样例 1

2
3 4
4 2

输入样例 2

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

输出样例 2

3
2 3
7 3