선물 교환 파티

TKB 시의 한 학교에서 선물 교환 파티를 연다.

친한 친구 사이인 학생 쌍마다 이 파티에서 선물을 하나 건넨다. 한쪽이 다른 쪽에게 주고, 반대 방향으로는 주지 않는다. 각 쌍에서 누가 선물을 받을지는 파티 전에 미리 정해 둔다. 이 밖의 선물 교환은 없다.

각 쌍이 방향을 아무렇게나 정하면 선물을 잔뜩 받는 학생이 나오고, 몇 개 못 받거나 하나도 못 받는 학생도 나온다.

모든 친구 쌍의 선물 방향을 정해서, 학생이 받은 선물 개수의 최댓값과 최솟값의 차이를 가장 작게 만들려고 한다. 그 차이가 최소일 때 받은 선물 개수의 최솟값과 최댓값을 구하라. 차이가 최소인 방법이 여럿이면, 받은 선물 개수의 최솟값이 가장 큰 방법을 고른다.

입력은 데이터 집합 최대 10개로 이루어진다. 각 데이터 집합의 형식은 다음과 같다.

n m
u1 v1
...
um vm

$n$은 학생 수, $m$은 친구 관계의 수다 ($2 \le n \le 100$, $1 \le m \le n(n-1)/2$). 학생은 1 이상 $n$ 이하의 정수로 나타낸다. 이어지는 $m$개의 줄은 친구 관계를 나타낸다. 각 $i$에 대해 학생 $u_i$와 학생 $v_i$는 친한 친구이고 $u_i < v_i$다. 같은 친구 관계가 두 번 이상 주어지지는 않는다. 친구가 한 명도 없는 학생이 있을 수 있다.

0 두 개가 적힌 줄에서 입력이 끝난다.

각 데이터 집합마다 정수 두 개 $l$과 $h$를 공백 하나로 구분해 한 줄에 출력한다. $l$은 학생이 받은 선물 개수의 최솟값, $h$는 최댓값이다.