#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
#define NMAX 5005
#define MMAX 1000005

int n, m, cost[MMAX], nrcomp, t[NMAX], h[NMAX], maxim = -1, far, dmax, D = -1;
bool viz[NMAX];
vector<int> ad[NMAX];
queue<int> q;

void init(){
    for(int i=1; i<=n; i++){
        t[i] = i;
        h[i] = 1;
        cost[i] = 1;
    }
}

int gaseste(int a){
    while(a != t[a]){
        a = t[a];
    }
    return a;
}

void unite(int a, int b){
    nrcomp--;
    if(h[a] == h[b]){
          t[b] = a;
          h[a]++;
    }else
    if(h[a] > h[b]){
        t[b] = a;
    }else{
        t[a] = b;
    }
}

void BFS(int nod){
  q.push(nod);
  viz[nod] = 1;
  int i;
  while(!q.empty()){
    nod = q.front();
    if(dmax < cost[nod]){
      dmax = cost[nod];
      far = nod;
    }
    for(i=0; i<ad[nod].size(); i++){
      if(!viz[ ad[nod][i] ]){
        viz[ ad[nod][i] ] = 1;
        cost[ ad[nod][i] ] = cost[nod] + 1;
        q.push( ad[nod][i] );
      }
    }
    q.pop();
  }
}

int main(){

    int x, y, tx, ty, i;
    FILE *fin, *fout;
    fin = fopen("feisbuc.in", "r");
    fout = fopen("feisbuc.out", "w");

    fscanf(fin, "%d %d", &n, &m);
    nrcomp = n;
    init();

    for(i=1; i<=m; i++){
        fscanf(fin, "%d %d", &x, &y);
        tx = gaseste(x);
        ty = gaseste(y);
        ad[x].push_back(y);
        ad[y].push_back(x);
        if(tx != ty)
            unite(tx, ty);
    }

    for(i=1; i<=n; i++){
      if(!viz[ t[i] ]){
          dmax = -1;
          far = t[i];
          BFS( t[i] );
          memset(viz, false, sizeof(viz));
          for(int j=1; j<=n; j++)
            cost[j] = 1;
          BFS(far);
          if(dmax > D)
            D = dmax;
      }
    }

    maxim = D/2 + 1;
    fprintf(fout, "%d %d", nrcomp, maxim);

    fclose(fin);
    fclose(fout);

    return 0;
}