#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int Nmax = 100005;

int n, m;
int grad_nod[Nmax];
vector<int> graf[Nmax];

int nrMax(int len){
    int nod, cate;
    queue<int> q;

    for(int i = 1; i <= n; i++){
        grad_nod[i] = graf[i].size();

        if(grad_nod[i] < len){
            grad_nod[i] = -1;
            q.push(i);
        }
    }

    while(!q.empty()){
        nod = q.front();
        q.pop();

        for(int vecin : graf[nod]){
            if(grad_nod[vecin] != -1){
                grad_nod[vecin]--;
                if(grad_nod[vecin] < len){
                    grad_nod[vecin] = -1;
                    q.push(vecin);
                }
            }
        }
    }

    cate = 0;
    for(int i = 1; i <= n; i++){
        if(grad_nod[i] != -1){
            cate++;
        }
    }

    return cate;
}

int main(){
    ifstream fin("gminmax.in");
    ofstream fout("gminmax.out");

    int a, b, lft, rgt, sol, mid, cate, sol_cate;

    fin >> n >> m;
    for(int i = 0; i < m; i++){
        fin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    lft = 1;
    rgt = m;
    sol = -1;
    sol_cate = -1;
    while(lft <= rgt){
        mid = (lft + rgt) / 2;
        cate = nrMax(mid);

        if(cate == 0){
            rgt = mid - 1;
        }
        else{
            sol = mid;
            sol_cate = cate;
            lft = mid + 1;
        }
    }

    fout << sol << " " << sol_cate;

    return 0;
}