分数: 900 点
问题陈述
高桥决定制作一个 圣诞树 AtCoder, Inc. 的圣诞晚会
圣诞树是一棵有 N 顶点编号 1 通过 N 和 N-1 边,其 i第边缘 (1\leq i\leq N-1) 连接顶点 a_i 和 b_i.
他想做一个如下:
- 指定两个非负整数 A 和 B.
- 准备 A 圣诞路径 其长度最多为 B。这里,一条漫长的圣诞之路 X 是一个图表 X+1 顶点和 X 边,如果我们正确地对顶点进行编号 1 通过 X+1, i第边缘 (1\leq i\leq X) 将连接 Vertex i 和 i+1.
- 重复以下操作,直到拥有一棵连通树:
- 选择两个顶点 x 和 y 属于不同的连接组件。结合 x 和 y 进入一个顶点。更准确地说,对于每条边 (p,y) 事件到顶点 y,添加边缘 (p,x)。然后,删除顶点 y 和所有入射到的边 y.
- 对树中的顶点进行正确编号。
Takahashi 想找到字典顺序最小的一对 (A,B) 这样他就可以制作一棵圣诞树,即找到最小的 A,并找到最小的 B 条件是 A 被最小化。
帮他解决这个问题。
约束
- 2 \leq N \leq 10^5
- 1 \leq a_i,b_i \leq N
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
a_1 b_1
:
a_{N-1} b_{N-1}
输出
对于字典顺序最小的 (A,B),打印 A 和 B 之间有一个空格。
示例输入 1
7 1 2 2 3 2 4 4 5 4 6 6 7
示例输出 1
3 2
我们可以制作一棵圣诞树,如下图所示:

示例输入 2
8 1 2 2 3 3 4 4 5 5 6 5 7 5 8
示例输出 2
2 5
示例输入 3
10 1 2 2 3 3 4 2 5 6 5 6 7 7 8 5 9 10 5
示例输出 3
3 4