Gift Exchange Party

A school in TKB City holds a gift exchange party.

Every pair of students who are close friends passes one gift at this party. One of the two gives a gift to the other, and nothing goes back the other way. Which student of each pair receives the gift is fixed before the party. No other gift passes between students.

If every pair picked its direction at random, one student could end up with a heap of gifts while another gets one or none at all.

Choose the gift direction for every friend pair so that the difference between the largest and the smallest number of gifts a student receives is as small as possible. Report the smallest and the largest number of gifts received once that difference is minimized. When several choices reach that minimum difference, take the one whose smallest number of received gifts is largest.

The input consists of at most 10 datasets. Each dataset has the following format.

n m
u1 v1
...
um vm

$n$ is the number of students and $m$ is the number of friendship relations ($2 \le n \le 100$, $1 \le m \le n(n-1)/2$). Students are denoted by integers between 1 and $n$, inclusive. The following $m$ lines describe the friendship relations: for each $i$, student $u_i$ and student $v_i$ are close friends, and $u_i < v_i$. The same friendship relation never appears more than once. A student may have no friends at all.

A line containing two zeros ends the input.

For each dataset, print one line containing two integers $l$ and $h$ separated by a single space. Here $l$ is the smallest and $h$ is the largest number of gifts received by a student.