#955. 会议

会议

题目描述

有一个村庄居住着 nn 个村民,有 n−1n-1 条路径使得这 nn 个村民的家连通,每条路径的长度都为 11。现在村长希望在某个村民家中召开一场会议,村长希望所有村民到会议地点的距离之和最小,那么村长应该要把会议地点设置在哪个村民的家中,并且这个距离总和最小是多少?若有多个节点都满足条件,则选择节点编号最小的那个点。

输入格式

第一行,一个数 nn,表示有 nn 个村民。

接下来 n−1n-1 行,每行两个数字 aa 和 bb,表示村民 aa 的家和村民 bb 的家之间存在一条路径。

输出格式

一行输出两个数字 xx 和 yy。

xx 表示村长将会在哪个村民家中举办会议。

yy 表示距离之和的最小值。

样例

4
1 2 
2 3 
3 4 
2 4

题目来源:洛谷 P1395