题目背景
天灾军团又来袭击艾泽拉斯了，这一次，没有五大守护巨龙的守护，甚至还有各大职业的顶尖级的人物成为了死亡骑士，比如说
死亡先知萨尔(萨满祭司)
污染者玛法里奥(德鲁伊)
黑锋骑士乌瑟尔(圣骑士)
虚空之影瓦莉拉(潜行者)
冰霜女巫吉安娜(法师)
死亡猎手雷克萨(猎人)
天灾领主加鲁尔什(战士)
暗影收割者安度因(牧师)
鲜血掠夺者古尔丹(术士)
达拉然的大法师安东尼达斯以及卡拉赞的守护者麦迪文为了艾泽拉斯人民的安全，一人开辟了一个传送门，使得人们可以从传送门撤离避免遭到天灾军团的屠戮。
题目描述
艾泽拉斯共有 个区域(编号 到 )，有 条道路，每条路连接两个区域，使得这 个区域两两可达，从道路的一边走到另一边需要花费一个单位时间。
形象的说，你可以将艾泽拉斯看成一颗 个节点的树，走一条边需要花费一个单位时间，由于安东尼达斯和麦迪文想要所有艾泽拉斯人民全部撤离到传送门的时间最短。所以，安东尼达斯和麦迪文会向你提出 个问题,你需要回答如果在 处分别开辟传送门，那么所有艾泽拉斯人民全部撤离到传送门的最短时间是多少(假设每个区域都有人并且道路的容量是无限的)。
