CF1294F.Three Paths on a Tree

You are given an unweighted tree with $n$ vertices. Recall that a tree is a connected undirected graph without cycles.

Your task is to choose three distinct vertices $a, b, c$ on this tree such that the number of edges which belong to at least one of the simple paths between $a$ and $b$, $b$ and $c$, or $a$ and $c$ is the maximum possible. See the notes section for a better understanding.

The simple path is the path that visits each vertex at most once.

给你一棵包含 $n$ 个顶点的无权树。注意，树是一种连通的无向无环图。

你的任务是在该树上选出三个互不相同的顶点 $a, b, c$，使得至少属于以下某条简单路径的边数达到最大：$a$ 与 $b$ 之间的简单路径、$b$ 与 $c$ 之间的简单路径，或 $a$ 与 $c$ 之间的简单路径。详见“说明”部分以获得更清晰的理解。

简单路径是指每顶点至多被访问一次的路径。

The first line contains one integer number $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

Next $n - 1$ lines describe the edges of the tree in form $a_i, b_i$ ($1 \le a_i$, $b_i \le n$, $a_i \ne b_i$). It is guaranteed that given graph is a tree.

第一行包含一个整数 $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$）。保证给定的图是一棵树。

In the first line print one integer $res$ — the maximum number of edges which belong to at least one of the simple paths between $a$ and $b$, $b$ and $c$, or $a$ and $c$.

In the second line print three integers $a, b, c$ such that $1 \le a, b, c \le n$ and $a \ne, b \ne c, a \ne c$.

If there are several answers, you can print any.

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

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

若存在多个答案，输出任意一个即可。

The picture corresponding to the first example (and another one correct answer):

If you choose vertices $1, 5, 6$ then the path between $1$ and $5$ consists of edges $(1, 2), (2, 3), (3, 4), (4, 5)$, the path between $1$ and $6$ consists of edges $(1, 2), (2, 3), (3, 4), (4, 6)$ and the path between $5$ and $6$ consists of edges $(4, 5), (4, 6)$. The union of these paths is $(1, 2), (2, 3), (3, 4), (4, 5), (4, 6)$ so the answer is $5$. It can be shown that there is no better answer.

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

若选择顶点 $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$。可以证明不存在更优的答案。