問題
背景
グラフ塗り職人のイクタ君は、顧客の要望にできるだけ忠実に色を塗るため、グラフの塗り方について日々研究をしている。 今日は、頂点を二色に塗りわけた時、両端の頂点の色が異なる辺の数に注目することにした。
課題
n 個の頂点と n 本の辺からなる連結なグラフが存在する。このグラフには両端が同じ頂点に繋がっている辺は存在せず、またある 2 つの頂点の間に複数の辺が存在することも無い。
このグラフのすべての頂点を赤色または青色に塗る。この時、赤色に塗られた頂点も青色に塗られた頂点も一つ以上存在するようにする。そのような条件を満たすように塗った時の、両端の頂点が別々に塗られている辺の数の最小値と最大値をそれぞれ求めよ。
なお、この問題はグラフの最小カットおよび最大カット (日本語版 Wikipedia) を求める問題と同値である。
入力
入力は以下の形式で与えられる。
n a1 b1 : an bn
1 行目に頂点および辺の数 n (3 ≤ n ≤ 100,000) が書かれている。 2 行目から n+1 行目には、2 つの整数 ai, bi が書かれていて、頂点 ai と頂点bi を結ぶ辺が存在することを表している。
制約
- 3 ≤ n ≤ 100,000
- 1 ≤ ai,bi ≤ n
- 両端が同じ頂点に繋がっている辺は存在しない。
- ある2つの頂点の間に複数の辺は存在しない。
出力
両端の頂点が別々に塗られている辺の数の最小値 min と最大値 MAX を空白区切りで 1 行に出力せよ。
入出力例
入力例1
4 1 2 2 3 3 1 1 4
出力例1
1 3