AT_arc088_d [ARC088F] Christmas Tree

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

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ a_i,b_i\ \leq\ N $ - 与えられるグラフは木である ### Sample Explanation 1 下の図のような方法で、クリスマスツリーを作ることができます。 !\[\](https://img.atcoder.jp/arc088/96f78221624d6a13628f6052f5db697d.png)