CF1073F.Choosing Two Paths

You are given an undirected unweighted tree consisting of $n$ vertices.

An undirected tree is a connected undirected graph with $n - 1$ edges.

Your task is to choose two pairs of vertices of this tree (all the chosen vertices should be distinct) $(x_1, y_1)$ and $(x_2, y_2)$ in such a way that neither $x_1$ nor $y_1$ belong to the simple path from $x_2$ to $y_2$ and vice versa (neither $x_2$ nor $y_2$ should not belong to the simple path from $x_1$ to $y_1$).

It is guaranteed that it is possible to choose such pairs for the given tree.

Among all possible ways to choose such pairs you have to choose one with the maximum number of common vertices between paths from $x_1$ to $y_1$ and from $x_2$ to $y_2$. And among all such pairs you have to choose one with the maximum total length of these two paths.

It is guaranteed that the answer with at least two common vertices exists for the given tree.

The length of the path is the number of edges in it.

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

给你一棵包含 $n$ 个顶点的无向无权树。

无向树是指一个具有 $n - 1$ 条边的连通无向图。

你的任务是为此树选出两对顶点（所有被选中的顶点必须互不相同）：$(x_1, y_1)$ 和 $(x_2, y_2)$，满足以下条件：

• $x_1$ 和 $y_1$ 均不在 $x_2$ 到 $y_2$ 的简单路径上；
• $x_2$ 和 $y_2$ 均不在 $x_1$ 到 $y_1$ 的简单路径上。

题目保证对于给定的树，总存在满足上述条件的顶点对。

在所有满足条件的方案中，你需要选择两条路径（即 $x_1$ 到 $y_1$ 的路径与 $x_2$ 到 $y_2$ 的路径）公共顶点数最多的一种；
若存在多个方案具有相同的最大公共顶点数，则在这些方案中，再选择两条路径的总长度（即边数之和）最大的一种。

题目保证给定的树存在至少具有两个公共顶点的最优解。

路径的长度定义为该路径所含边的数量。

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

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

Each of the next $n - 1$ lines describes the edges of the tree.

Edge $i$ is denoted by two integers $u_i$ and $v_i$, the labels of vertices it connects ($1 \le u_i, v_i \le n$, $u_i \ne v_i$).

It is guaranteed that the given edges form a tree.

It is guaranteed that the answer with at least two common vertices exists for the given tree.

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

接下来的 $n - 1$ 行描述树的边。

第 $i$ 条边由两个整数 $u_i$ 和 $v_i$ 表示，即该边所连接的两个顶点的编号（$1 \le u_i, v_i \le n$，且 $u_i \ne v_i$）。

保证给定的边构成一棵树。

保证对于给定的树，存在至少两个公共顶点的答案。

Print any two pairs of vertices satisfying the conditions described in the problem statement.

It is guaranteed that it is possible to choose such pairs for the given tree.

输出任意两对满足题目描述条件的顶点。

保证对于给定的树，总能选出满足条件的这样的顶点对。

The picture corresponding to the first example:

The intersection of two paths is $2$ (vertices $1$ and $4$) and the total length is $4 + 3 = 7$.

The picture corresponding to the second example:

The intersection of two paths is $2$ (vertices $3$ and $4$) and the total length is $5 + 3 = 8$.

The picture corresponding to the third example:

The intersection of two paths is $3$ (vertices $2$, $7$ and $8$) and the total length is $5 + 5 = 10$.

The picture corresponding to the fourth example:

The intersection of two paths is $5$ (vertices $1$, $2$, $3$, $4$ and $5$) and the total length is $6 + 6 = 12$.

第一个示例对应的图片：

两条路径的交集大小为 $2$（顶点 $1$ 和 $4$），总长度为 $4 + 3 = 7$。

第二个示例对应的图片：

两条路径的交集大小为 $2$（顶点 $3$ 和 $4$），总长度为 $5 + 3 = 8$。

第三个示例对应的图片：

两条路径的交集大小为 $3$（顶点 $2$、$7$ 和 $8$），总长度为 $5 + 5 = 10$。

第四个示例对应的图片：

两条路径的交集大小为 $5$（顶点 $1$、$2$、$3$、$4$ 和 $5$），总长度为 $6 + 6 = 12$。