← 返回题目列表

AtCoder · arc088_d

F. 圣诞树

中文机器翻译题面 查看原题

分数: 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