有 个人,编号为 到 。第 个人希望与第 个人变得亲近。
可以在任意两个不同的人之间建立朋友关系。朋友关系是双向的,同一对人之间最多建立一个关系。定义两个人 的亲密度 为沿朋友关系从第 个人到第 个人所需经过的最少关系数。当 时,。
建立恰好 个朋友关系,使所有人相互连通,并最小化
输出这个最小值和一组达到最小值的朋友关系。允许 。
输入格式如下:
第一行输出亲密度总和的最小值。
接下来 行,每行输出用空格分隔的两个编号 ,表示建立朋友关系。必须满足 且 。同一对人的关系不能重复输出,且所有人必须连通。
输出的朋友关系中,亲密度总和必须等于第一行的最小值。如果存在多组最优解,可以输出任意一组。关系的输出顺序及每条关系两个端点的顺序均不限。
| 4 | 38 | 추가적인 제약이 없다. |