给你一棵带有 $$$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 \ne b_i$$$) 的形式描述树的边缘。保证给定的图是一棵树。
输出
在第一行中打印一个整数 $$$res$$$ — 属于 $$$a$$$ 和 $$$b$$$、$$$b$$$ 和 $$$c$$$ 或 $$$a$$$ 和 $$$c$$$ 之间的至少一个简单路径的最大边数。
在第二行中打印三个整数 $$$a, b, c$$$ 使得 $$$1 \le a, b, c \le n$$$ 和 $$$a \ne, b \ne c, a \ne c$$$。
如果有多个答案,您可以打印任何答案。
示例
输入 #1
8 1 2 2 3 3 4 4 5 4 6 3 7 3 8
输出 #1
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$$$。可以证明,没有更好的答案。