题目描述

题目译自 XXII Olimpiada Informatyczna — III etap Modernizacja autostrady

字节城有 $n$ 座城市，连接它们的道路网络密集但老旧，因此近年新建了 $n-1$ 条现代化高速公路，确保任意两城可通过高速公路直达。然而，高速公路收费高昂，引发市民不满。交通部长决定优化高速公路网，平息民怨。年度预算仅允许拆除一条高速公路并新建一条（可能在原位置但更现代化）。他希望选择拆建方案，保证任意两城仍可通过高速公路连通，且两城间最长路径上的高速公路数尽可能少，称为乐观方案。

与此同时，财政部长希望通过现代化提升收费收入，目标是保证连通性，但使两城间最长路径的高速公路数尽可能多，称为悲观方案。

两位部长的计划传到媒体，记者 Bajtazar 正撰写相关报道，需展示最乐观和最悲观的现代化方案。请你编写程序，为他的文章提供准确数据。

输入格式

第一行包含一个整数 $n$ $(3 \leq n \leq 500000)$，表示字节城城市数量，城市编号为 $1$ 到 $n$。

接下来的 $n-1$ 行描述高速公路，第 $i$ 行包含两个整数 $a_i, b_i$ $(1 \leq a_i, b_i \leq n, a_i \neq b_i)$，表示 $a_i$ 号和 $b_i$ 号城市间有高速公路。

输出格式

第一行包含五个整数 $k, x_1, y_1, x_2, y_2$，描述乐观方案：两城间最长路径的高速公路数为 $k$，拆除 $x_1$ 和 $y_1$ 间的高速公路，建设 $x_2$ 和 $y_2$ 间的高速公路。

第二行以相同格式描述悲观方案。拆建城市对可任意排序。若有多种方案，输出任意一种。

程序需输出两行，每行答案独立评分。若仅一个方案正确，得测试点一半分数，此时另一行内容不影响评分。

6
1 2
2 3
2 4
4 5
6 5

3 4 2 2 5
5 2 1 1 6

• 乐观方案：拆除 $4$ 和 $2$ 间高速公路，建设 $2$ 和 $5$ 间高速公路，最长路径高速公路数为 $3$。
• 悲观方案：拆除 $2$ 和 $1$ 间高速公路，建设 $1$ 和 $6$ 间高速公路，最长路径高速公路数为 $5$。

附加样例

1. $n=5$，星型网络；
2. $n=1000$，链型网络；
3. $n=2^{18}$，每座城市 $i>1$ 通过高速公路连接到城市 $\lfloor \frac{i}{2} \rfloor$。

数据范围与提示

对于 $30\%$ 的数据，$n \leq 1000$。