给你一个由 $$$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$$$。