// Problem H. Gift Exchange Party / プレゼント交換会

#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;
  // cur番目のノードから連結しているプレゼント数が閾値 (th) 以下のノードを深さ優先探索
  function<bool(int, int)> dfs = [&](int cur, int th) {
    // cur番目のノードのプレゼント数が閾値以下ならばプレゼント数を増やしてretrun
    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);
    // プレゼント数が (プレゼント数の最大値 - 2) 以下のノードを探索
    // 見つからなければ終了
    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;
}