题目描述

每个测试的时间限制：2 秒
每个测试的内存限制：256 兆字节

给你一棵无权的树，包含 $n$ 个顶点。回忆一下，树是一个连通的无环无向图。

你的任务是选择三个不同的顶点 $a, b, c$，使得至少属于 $a$ 与 $b$、$b$ 与 $c$、$a$ 与 $c$ 之间的简单路径之一的边的数量最大。有关更好的理解，请参见说明部分。

简单路径是指每个顶点至多经过一次的路径。

输入格式

第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）—— 树中顶点的数量。

接下来的 $n-1$ 行，每行以 $a_i, b_i$ 的形式描述树的一条边（$1 \le a_i, b_i \le n$，$a_i \neq b_i$）。保证给定的图是一棵树。

输出格式

第一行输出一个整数 $res$—— 至少属于 $a$ 与 $b$、$b$ 与 $c$、$a$ 与 $c$ 之间的简单路径之一的边的最大数量。

第二行输出三个整数 $a, b, c$，满足 $1 \le a, b, c \le n$ 且 $a \neq b$、$b \neq c$、$a \neq c$。

如果有多个答案，你可以输出任意一个。

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

5
1 8 6

说明

第一个示例对应的图示（以及另一个正确答案）如下：

如果你选择顶点 $1, 5, 6$：

• $1$ 到 $5$ 的路径包含边 $(1,2), (2,3), (3,4), (4,5)$；
• $1$ 到 $6$ 的路径包含边 $(1,2), (2,3), (3,4), (4,6)$；
• $5$ 到 $6$ 的路径包含边 $(4,5), (4,6)$。

这些路径的并集是 $(1,2), (2,3), (3,4), (4,5), (4,6)$，因此答案为 $5$。可以证明不存在更好的答案。