using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#define nmax 200005
#define oo 0x3f3f3f3f
#define pb push_back

#define common int m=(l+r)/2, L=2*n, R=L+1
vector<int> G[nmax];
int N,M,nh;
int H[3*nmax];
ofstream fout("gminmax.out");

void update(int n,int ql,int l,int r)
{
    if(l>=r)
    {

        return;

    }

    common;
    /*
    if(full[n]==1)
    {full[n]=0;
    full[L]=full[R]=1;
    H[L]=H[R]=H[n];
    }
    */
    if(ql<=m) update(L,ql,l,m);
    else update(R,ql,m+1,r);
         if(G[H[L]].size()==0 && G[H[R]].size()==0)
            H[n]=H[L];
           else if(G[H[L]].size()==0 )  H[n]=H[R];
             else if( G[H[R]].size()==0) H[n]=H[L];
               else if(G[H[L]].size()<=G[H[R]].size()) H[n]=H[L];
                   else H[n]=H[R];

}

void build(int n,int l,int r)
{
    if(l>=r) {H[n]=l;
    //cout<<G[H[n]].size()<<" ";
     return;}

    common;
    build(L,l,m);
    build(R,m+1,r);

         if(G[H[L]].size()==0 && G[H[R]].size()==0)
            H[n]=H[L];
           else if(G[H[L]].size()==0 )  H[n]=H[R];
             else if( G[H[R]].size()==0) H[n]=H[L];
               else if(G[H[L]].size()<=G[H[R]].size()) H[n]=H[L];
                   else H[n]=H[R];

}

void solve()
{int maxi=-oo,cont,loc,u;
vector<int>::iterator it,jt;
//cout<<1;

    build(1,1,N);
    //cout<<"\nok";
    nh=N;
    while(nh--)
    {

        u=H[1];
        loc=G[u].size();
        if(maxi<loc)
        {
            maxi=loc;
            cont=nh;
        }
        //cout<<nh<<" "<<u<<" "<<loc<<" "<<cont<<"\n";
        for(it=G[u].begin();it<G[u].end();it++)
        {
            for(jt=G[*it].begin();jt<G[*it].end();jt++)
            {
                if(*jt==u)
                {
                    G[*it].erase(jt);
                    update(1,*it,1,N);

                }
            }
        }
        //cout<<" \n";
            //build(1,1,N);
            //cout<<"\n";

        G[u].clear();
        //cout<<G[u].size();

        update(1,u,1,N);

    }
    fout<<maxi<<" "<<cont+1<<"\n";
}

void cit()
{
    int i,x,y;
   ifstream fin("gminmax.in");
   fin>>N>>M;
   for(i=1;i<=M;i++)
   {
       fin>>x>>y;
       G[x].pb(y);
       G[y].pb(x);

   }
   fin.close();
}

int main()
{
     for(int i=1;i<=nmax;i++)
      G[0].pb(0);
    cit();
    solve();
    fout.close();
    return 0;
}