联盟

league.cpp/in/out

Special Judge

• 时间限制：1s
• 内存限制：128MB

题目描述

G 国周边的 $n$ 个小国家构成一个联盟以抵御 G 国入侵，为互相支援，他们建立了 $n-1$ 条双向通路，使得任意两个国家可以经过通路相互到达。

当一个国家受到攻击时，所有其它国家都会沿着最短路径前往这个国家进行支援，经过每条通路所需的时间均为 1。定义一个国家的危险程度为所有国家全部赶到需要的最短时间，联盟的危险程度为所有国家的危险程度的最大值。

为了降低危险程度，联盟决定断开一条通路并任意连接一条通路，使得危险程度尽可能小，并要求改建完成之后任意两个国家可以经过通路互相到达。他们决定让你来设计方案，你需要告知在最优方案中可能断开哪些边，并给出任意一组最优方案。

输入格式

第一行一个正整数 $n$。

接下来 $n-1$ 行每行两个正整数，表示一条 $u_i, v_i$ 之间的边。

输出格式

输出第一行一个整数表示最小危险程度。

第二行一个整数 $k$，表示可能被断开的边的数量，接下来 $k$ 个数，表示可能断开的边的编号，按升序输出。

接下来一行四个正整数表示一组最优方案，分别表示断开和新建的边的端点，只需给出任意一组合法的方案即可。

样例输入

4
1 2
2 3
3 4

样例输出

2
2 1 3
3 4 4 2

数据范围

• 对于 20% 的数据，$n \le 30$。
• 对于 40% 的数据，$n \le 300$。
• 对于 60% 的数据，$n \le 3000$。
• 对于 100% 的数据，$n \le 300000$。

提示

如果你的答案仅第一行正确，你可以获得 25% 的分数；

如果你的答案仅前两行正确，你可以获得 50% 的分数。

为保证得到部分分请确保提交程序的输出格式符合题目要求。