CF700B Connecting Universities

树之王国是一个由n-1条双向路连接着n个城镇的国家，任意两个城镇间都是联通的。 在树之王国共有2k所大学坐落于不同的城镇之中。 最近，树国总统颁布了一项在大学间建立高速信息网络的法案。教育部部长以他自己的方式理解了这项法案，他发现用电缆连接各所学校是绰绰有余的。形式上来说，这项法案安排的任务的确被完成了！(贪官...) 为了能尽可能多地获取财政预算，部长打算把大学分成一对一对的，使得在各所学校间建立连接所需的电缆最长。换句话说，k对大学间的距离总和越大越好。 帮助部长完成这个任务。当然了，每所大学不能重复出现在多对里。你可以认为每条路的长度均为1。

无

无

下图展示了在样例一的一种可能的结果。如果你把坐落于1号城镇的大学和坐落于6号城镇的大学连接在一起，把坐落于2号城镇的大学和坐落于5号城镇的大学连接在一起，那么距离总和为6，在样例一中是最大距离总和。