問題文

$N$ 頂点の木があり、頂点には $1,2,...,N$ と番号が振られています。

$i$ 番目の辺は頂点 $a_i$ と $b_i$ をつないでいます。

HalcとSappはこの木と駒を使ってゲームをします。

進行は以下の通りです。

• はじめ、頂点 $1$ に駒がある。
• HalcとSappが交互に駒を隣の頂点へ動かす。複数の行き先がある場合はどこに行ってもよい。
• 一回通った頂点には二度と立ち入ることができない。
• 動けなくなったらゲーム終了。

どちらかが駒を動かすのを $1$ ターンと数えます。

Halcはゲームが終了するまでのターン数を最大化、Sappは最小化しようとしています。

Halcが先手、後手の場合それぞれにおいて、両者が最適に行動した時のゲームが終了するまでのターン数を出力してください。

入力

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$

• $1\leqq N\leqq 2\times 10^5$
• $1\leqq a_i,b_i\leqq N$
• 与えられるグラフは木である
• 入力はすべて整数

出力

2行出力してください。

1行目にはHalcが先手の場合、2行目にはHalcが後手の場合のターン数を出力してください。

サンプル

6
1 2
2 3
3 4
3 5
5 6

4
3

4
1 2
1 3
1 4

1
1

1

0
0