题目描述
给定一棵有 个节点的无根树,节点编号为 ,每条边的长度均为 。
对于树上的一个节点 ,定义它的偏心距为它到树上所有节点距离的最大值,记作
其中 表示 到 的唯一简单路径上的边数。
请你求出这棵树的中心:偏心距最小的节点。如果有多个节点的偏心距同时取到最小值,输出编号最小的那个。同时输出这个最小的偏心距。
输入格式
第一行一个正整数 ,表示节点数。
接下来 行,每行两个正整数 ,表示节点 与节点 之间有一条边。保证输入数据构成一棵树。
输出格式
一行两个整数,用一个空格隔开,依次表示树的中心编号和该节点的偏心距。
样例 1
输入:
5
1 3
3 5
5 2
5 4
输出:
3 2
说明:节点 到 、 的距离为 ,到 、 的距离为 ,偏心距为 ;节点 到 、 的距离为 ,到 的距离为 ,偏心距也为 。两者并列最小,取编号较小的 ,所以答案为 。
数据范围
- 对于 的数据,;
- 对于 的数据,;
- 对于 的数据,,,输入保证是一棵树。
注意: 时树中只有一个节点,此时中心为 ,偏心距为 。