Home => ProblemSet => 5.1-28:会议
Problem1877--5.1-28:会议

1877: 5.1-28:会议

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 4
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

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

Input

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

Output

一行输出两个数字 x 和 y。
x 表示村长将会在哪个村民家中举办会议。
y 表示距离之和的最小值。

Sample Input Copy

4
1 2 
2 3 
3 4 

Sample Output Copy

2 4

HINT

对于 70% 数据 n≤103
对于 100% 数据 n≤5×104

Source/Category

  DFS