パーティーに $n$ 人のゲストがいます。各ゲストは異なる 2 つの趣味を持っています。趣味の集合が同じゲストは 2 人いません。主催者は、同じグループのどの 2 人も共通の趣味を持つように、ゲストを 2 人または 3 人のグループに分けたいと考えています。つまり各グループは次のいずれかです。

• タイプ A: 共通の趣味を 1 つ持つ 2 人のグループ。

• タイプ B: 3 人全員に共通の趣味があるグループ。

• タイプ C: どの 2 人にも共通の趣味がある 3 人のグループ。ただしタイプ B の場合を除きます。

主催者は、どのグループにも割り当てられないゲストの人数 $\alpha$ をできるだけ小さくしたいと考えています。$\alpha$ が最小の解が複数ある場合、$\alpha$ を最小に保ったまま、解に使われるタイプ B のグループ数 $\beta$ を最小にする解を求める必要があります。この 2 つの数を求めるプログラムを書いてください。

図 15: 上の図は 3 番目のテストケースの異なる 2 つの解を示しています。右の解はタイプ B のグループを使わないので、左の解より良い解です。

入力

各テストケースは $n+1$ 行からなります。最初の行に 2 つの整数 $n,h$ が与えられ、続いて $n$ 行が与えられます。$(i+1)$ 行目には $1 \le x,y \le h$ を満たす 2 つの整数 $x,y$ が含まれ、$i$ 番目のゲストの趣味が $x$ と $y$ であることを表します。

制約

• $2 \le n \le 10^6$.

• $3 \le h \le 2n$.

出力

最良の解を求め、割り当てられないゲストの人数 $\alpha$ と、その解で使うタイプ B のグループ数 $\beta$ を出力してください。目的はまず $\alpha$ を最小にし、次に $\alpha$ を可能な最小値に保ちながら $\beta$ を最小にすることです。

入出力例

入力 1

2 4
1 2
3 4

出力 1

2 0

入力 2

2 3
1 2
3 1

出力 2

0 0

入力 3

5 5
1 2
2 3
2 4
5 2
5 4

出力 3

0 0