#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 5003;

int n,m;
vector<int> vecini[MAXN];
int grad[MAXN];


void citire()
{
    freopen("feisbuc.in","r",stdin);
    freopen("feisbuc.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x,y;
    for (int i = 1;i <= m;++i)
    {
        scanf("%d%d",&x,&y);
        vecini[x].push_back(y);
        vecini[y].push_back(x);
        ++grad[x];
        ++grad[y];
    }
}


int d[MAXN] = {0};
int raspuns = 0;

void bfs(int &ultim, int &diametru)
{
    int coada[MAXN] = {0};
    int p = 1, q = 1;
    bool vizitat[MAXN] = {0};
    coada[1] = ultim;
    vizitat[ultim] = true;
    d[ultim] = 1;
    diametru = 1;
    while(p <= q)
    {
        int nod = coada[p];
        ++p;
        for (unsigned int i = 0;i < vecini[nod].size();++i)
        {
            int vecin = vecini[nod][i];
            if (vizitat[vecin])
                continue;
            d[vecin] = d[nod] + 1;
            vizitat[vecin] = true;
            coada[++q] = vecin;
            if (d[vecin] > diametru)
            {
                diametru = d[vecin];
                ultim = vecin;
            }
        }
    }
}

void prelucrare()
{
    for (int i = 1;i <= n;++i)
        if (d[i] == 0)
        {
            int ultim = i;
            int diametru = 0;
            bfs(ultim,diametru);
            bfs(ultim, diametru);
            if (diametru > raspuns)
                raspuns = diametru;
        }
}

int main()
{
    citire();
    prelucrare();
    printf("%d %d\n",n - m, raspuns / 2 + 1);
    return 0;
}