题目描述

高橋君は、AtCoder 社のクリスマスパーティーに向けて、クリスマスツリーを作ることにしました。

クリスマスツリーとは 頂点に $1$ から $N$ まで番号付けられた $N$ 頂点 $N-1$ 辺の木で、 $i(1\leq\ i\leq\ N-1)$ 本目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。

高橋君は、以下の方法でクリスマスツリーを作りたいです。

• $2$ つの非負整数 $A,B$ を指定する。
• 長さ $B$ 以下のクリスマスパスを $A$ 個用意する。ただし、長さ $X$ のクリスマスパスとは、$X+1$ 頂点 $X$ 辺からなるグラフであって、頂点に $1$ から $X+1$ までの番号を適切につければ、$i(1\leq\ i\leq\ X)$ 本目の辺が頂点 $i$ と頂点 $i+1$ を結んでいるようにできるものを指す。
• 以下の操作を、全体が連結になるまで繰り返す。
  • 異なる連結成分に属する $2$ 頂点 $x,y$ をとる。頂点 $x$ と頂点 $y$ をまとめて $1$ つの頂点にする。より正確には、頂点 $y$ に接続するすべての辺 $(p,y)$ について辺 $(p,x)$ を追加したあと、頂点 $y$ と、$y$ に接続する辺をすべて削除する。
• 出来上がった木の各頂点に、適当な番号をつける。

高橋君は、クリスマスツリーを作ることのできるような組 $(A,B)$ のうち、辞書順最小のものを求めたいです。 すなわち、$A$ の最小値を求め、$A$ の最小値を達成するという条件のもとで $B$ の最小値も求めたいです。

高橋君にかわって、この問題を解いてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $b_1$ : $a_{N-1}$ $b_{N-1}$

输出格式

辞書順最小の $(A,B)$ に対し、$A,B$ を空白区切りで出力せよ。

题目大意

给定一棵 $N$ 个节点的树。用如下方法生成一棵与其相同的树：

• 首先生成 $A$ 个边数均不超过 $B$ 的链。
• 重复以下操作直到所有的点连通：
  • 选择两个当前属于不同连通块的点，将这两个点合并为一个点，所有原来与这两个点中的至少一个点有边的点与这个新点有边。
• 将点重新标号。

求出能够生成给定树的最小的 $A$ 值，在最小化 $A$ 的基础上最小化 $B$ 值。

对于 $100 \%$ 的数据，$2\le N\le 10^5$。

【输入格式】

第一行输入 $N$，随后 $N-1$ 行每行两个整数描述一条边。

【输出格式】

输出一行两个整数，题目所求的 $A$ 和 $B$。

7
1 2
2 3
2 4
4 5
4 6
6 7

3 2

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

2 5

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

3 4

提示

制約

• $2\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ a_i,b_i\ \leq\ N$
• 与えられるグラフは木である

Sample Explanation 1

下の図のような方法で、クリスマスツリーを作ることができます。