配点 : $900$ 点

問題文

高橋君は、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$ に接続する辺をすべて削除する。
• 異なる連結成分に属する $2$ 頂点 $x,y$ をとる。頂点 $x$ と頂点 $y$ をまとめて $1$ つの頂点にする。より正確には、頂点 $y$ に接続するすべての辺 $(p,y)$ について辺 $(p,x)$ を追加したあと、頂点 $y$ と、$y$ に接続する辺をすべて削除する。
• 出来上がった木の各頂点に、適当な番号をつける。

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

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

制約

• $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$ を空白区切りで出力せよ。

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