[ARC088F] Christmas Tree

给定一棵 $N$ 个节点的树。用如下方法生成一棵与其相同的树： - 首先生成 $A$ 个边数均不超过 $B$ 的链。 - 重复以下操作直到所有的点连通： - 选择两个当前属于不同连通块的点，将这两个点合并为一个点，所有原来与这两个点中的至少一个点有边的点与这个新点有边。 - 将点重新标号。 求出能够生成给定树的最小的 $A$ 值，在最小化 $A$ 的基础上最小化 $B$ 值。 对于 $100 \%$ 的数据，$2\le N\le 10^5$。 **【输入格式】** 第一行输入 $N$，随后 $N-1$ 行每行两个整数描述一条边。 **【输出格式】** 输出一行两个整数，题目所求的 $A$ 和 $B$。

[problemUrl]: https://atcoder.jp/contests/arc088/tasks/arc088_d 高橋君は、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 $ を空白区切りで出力せよ。

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 下の図のような方法で、クリスマスツリーを作ることができます。 !\[\](https://img.atcoder.jp/arc088/96f78221624d6a13628f6052f5db697d.png)