#P2067. [Poi2004]SZN

    ID: 1092 传统题 1000ms 64MiB 尝试: 267 已通过: 79 难度: 7 上传者: 标签>CF2300提高+/省选-奇偶性分析二分答案树形 DP排序贪心相向双指针二分查找支配关系Stage1

[Poi2004]SZN

[POI2004] SZN

题目描述

String-Toys joint-stock\text{String-Toys joint-stock} 公司需要你帮他们解决一个问题。

他们想制造一个没有环的连通图模型,每个图都是由一些顶点和特定数量的边构成。每个顶点都可以连向许多的其他顶点。一个图是连通且无环的,图是由许多的线做成的。一条线是一条连接图中两个顶点之间的路径。

由于一些技术原因,两条线之间不能有重叠的部分,要保证图中任意一条边都被且仅被一条线所覆盖。

做一个这样的图的模型的费用取决于用了多少条线以及最长的那条的长度(每条边的长度都为 11 )。

现在给你对应的图,请你编写一个程序,求出最少能用多少条线以及在用最少线的情况下最长的那根线最短可以为多少。

输入格式

第一行仅包含一个数 nn ,表示顶点的总数。顶点从 11 到 nn 进行编号。

接下来的 n−1n - 1 行描述这些边,每行两个数 aa 和 bb,表示顶点 aa 和顶点 bb 之间有一条边。

输出格式

输出两个数,最少用多少条线以及在用最少线的情况下最长线最短可以为多少.

样例 #1

样例输入 #1

9
7 8
4 5
5 6
1 2
3 2
9 8
2 5
5 8

样例输出 #1

4 2

提示

对于 100100 % 的数据:2≤n≤10000,1≤a,b≤n2 \le n \le 10000,1 \le a,b \le n 。

样例解释: