#include <bits/stdc++.h>
#define REP(i, n) for(auto i = 0; i < n; i++)
using namespace std;

auto solve(int n, vector<int>& p, vector<vector<bool>>& g) -> void {
  vector<bool> used;
  function<bool(int, int)> dfs = [&](int cur, int th) {
    if(p[cur] <= th) {p[cur]++; return true;}
    used[cur] = true;
    REP(prev, n) {
      if(!used[prev] && g[prev][cur] && dfs(prev, th)) {
        swap(g[prev][cur], g[cur][prev]);
        return true;
      }
    }
    return false;
  };
  while(true) {
    auto max_i = distance(p.begin(), max_element(p.begin(), p.end()));
    used.assign(n, false);
    if(!dfs(max_i, p[max_i] - 2)) break;
    p[max_i]--;
  }
}

auto main() -> int {
  int n, m, ui, vi;
  while(cin >> n >> m, n || m) {
    vector<int> p(n, 0);
    vector<vector<bool>> g(n, vector<bool>(n, false));
    REP(i, m) cin >> ui >> vi, g[ui - 1][vi - 1] = true, p[vi - 1]++;
    solve(n, p, g);
    auto ans = minmax_element(p.begin(), p.end());
    cout << *ans.first << ' ' << *ans.second << endl;
  }
  return 0;
}