← 返回题目列表

Codeforces · 1073/F

F. 选择两条路径

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

给你一个由 $$$n$$$ 个顶点组成的无向无权树。

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

你的任务是选择这棵树的两对顶点(所有选择的顶点应该是不同的)$$$(x_1, y_1)$$$和$$$(x_2, y_2)$$$,这样$$$x_1$$$和$$$y_1$$$都不属于从$$$x_2$$$到$$$x_2$$$的简单路径$$$y_2$$$ 反之亦然($$$x_2$$$ 和 $$$y_2$$$ 都不应该属于从 $$$x_1$$$ 到 $$$y_1$$$ 的简单路径)。

保证可以为给定的树选择这样的对。

在选择此类对的所有可能方法中,您必须选择从 $$$x_1$$$ 到 $$$y_1$$$ 以及从 $$$x_2$$$ 到 $$$y_2$$$ 的路径之间公共顶点数量最多的一种。在所有这些对中,您必须选择这两条路径总长度最大的一对。

保证给定的树存在至少具有两个公共顶点的答案。

路径的长度是其中的边数。

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

输入

第一行包含一个整数 $$$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$$$)。

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

保证给定的树存在至少具有两个公共顶点的答案。

输出

打印满足问题陈述中描述的条件的任意两对顶点。

保证可以为给定的树选择这样的对。

示例

输入 #1

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

输出 #1

3 6
7 5

输入 #2

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

输出 #2

2 9
6 8

输入 #3

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

输出 #3

10 6
4 5

输入#4

11
1 2
2 3
3 4
1 5
1 6
6 7
5 8
5 9
4 10
4 11

输出#4

9 11
8 10

注意

第一个例子对应的图片:

两条路径的交集为 $$$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$$$。