2679: 会议

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:1 解决:0

题目描述

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

输入

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

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

输出

一行输出两个数字x和y

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

y表示距离之和的最小值

样例输入 复制

4
1 2 
2 3 
3 4 

样例输出 复制

2 4

提示

70%数据n<=1000

100%数据n<=50000