← 返回题目列表

Codeforces · 1294/F

F. 树上的三条路

中文机器翻译题面 查看原题

给你一棵带有 $$$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$$$。可以证明,没有更好的答案。