第11题 编程实现： 蚂蚁王国住着N只蚂蚁，每只蚂蚁都有自己的领地，领地之间可以直接到达或经过其他领地间接到达，可以直接到达的领地之间的道路距离都为1，但所有领地都有一条唯一的最短路径可以相互到达

第11题Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

编程实现：Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

蚂蚁王国住着N只蚂蚁，每只蚂蚁都有自己的领地，领地之间可以直接到达或经过其他领地间接到达，可以直接到达的领地之间的道路距离都为1，但所有领地都有一条唯一的最短路径可以相互到达。Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

现要在 N块领地(依次编号为1~N)中，选出一块领地建立游乐场，使得所有蚂蚁到游乐场的最小距离总和是N种情况中最小的。Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

例如：N= 8，1~8号领地之间的连接关系：1和5、2和6、3和6、4和5、5和6、4和7、5和8。Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

如果将游乐场创建在 5号领地，最小距离总和为10。Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1号到5号距离为 1;Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

2号到5号距离为 2;Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

3号到5号距离次 2;Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

4号到5号距离为1;Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

6号到5号距离为 1;Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

7号到5号距离为 2;Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

8号到5号距离为1。Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

如果将游乐场创建在6号领地，最小距离总和为12。Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1号到6号距离为2;Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

2号到6号距离为1;Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

3号到6号距离为1;Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

4号到6号距离为2;Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

5号到6号距离为1;Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

7号到6号距离为3;Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

8号到6号距离为2;Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

可以发现，将游乐场创建在 5号领地，最小距离总和10是最小的，故输出10。Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入描述：Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

第一行输入一个正整数 N(2≤N≤20)，表示领地数量Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

接下来输入N-1行，每行包含两个正整数(1≤正整数≤N，两个正整数不相同)，表示两块领地相互之间可以直接到达，正整数之间以一个英文逗号隔开(数据保证 N 块领地相互之间可以到达)Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出描述：Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出一个整数，表示 N 种情况中最小距离总和的最小值Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

样例输入：Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

8Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

1,5Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

2,6Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

3,6Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

4,5Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

5,6Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

4,7Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

5,8Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

样例输出：10Qbn100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库