008 - プレゼント交換会

TKB市のある学校において，生徒同士のプレゼント交換会を行うことになった．

このパーティでは，親しい関係にある生徒のペアで，必ず 1 つのプレゼントが一人の生徒からもう一人の生徒へと渡され，逆向きはない． プレゼントの方向，すなわちペアのどちらがプレゼントをもらうかはあらかじめ決めておく． この他のプレゼントの交換はない．

それぞれのペアがプレゼントの方向をランダムに決めたら， 数えきれないプレゼントをもらう生徒がいる一方で，ほんの少ししか，あるいはまったくもらえない生徒も出てくるかもしれない．

あなたは親しい友達のペアすべてについてプレゼントの向きを決めて， ひとりの生徒がもらえるプレゼントの最小数と最大数の差をできるだけ小さくしたい． 差を最小にしたときにもらえるプレゼントの最小数と最大数を求めよ． 差が最小となるやり方が複数ある場合は，最小の受け取り数が最大となるものを求めよ．

入力は高々 10 個のデータセットからなる． 各データセットは次の形式で表される．

n m
u1 v1
...
um vm

n は生徒の人数，m は友人関係の数を表す (2 ≤ n ≤ 100, 1 ≤ m ≤ n (n-1)/2). 生徒は 1 から n までの整数で表される． 続く m 行は友人関係を表している：各 i について生徒 u_i と v_i が友人であることを意味する (u_i < v_i)． 同じ友人関係が複数回記述されることはない．

入力の終わりは，2つのゼロからなる行で表される．

各データセットについて，空白で区切られた 2 つの整数 l, h からなる行を出力せよ． ここで l はもらえるプレゼントが最も少ない生徒のプレゼント数，h はもらえるプレゼントが最も多い生徒のプレゼント数である．

3 3
1 2
2 3
1 3
4 3
1 2
1 3
1 4
4 6
1 2
1 3
1 4
2 3
3 4
2 4
0 0

1 1
0 1
1 2