#include <stdio.h>
#define NMAX 30002
#define INF 200000000

struct lista{long int nod;
             lista *urm;} *vf[NMAX];
struct nod{long int min,poz;};

nod arb[NMAX*3];

long int i,j,k,n,m,gr[NMAX],x,y;
long int clic[5];

void citire()
{
freopen("count.in","rt",stdin);
freopen("count.out","wt",stdout);
scanf("%ld %ld",&n,&m);
clic[1]=n;
clic[2]=m;
lista *p;
for (i=1;i<=m;i++)
        {
        scanf("%ld %ld",&x,&y);
        gr[x]++;gr[y]++;
        p=new lista;
        p->nod=x;
        p->urm=vf[y];
        vf[y]=p;

        p=new lista;
        p->nod=y;
        p->urm=vf[x];
        vf[x]=p;
        }
}

void build(long int nod, long int st, long int dr)
{
if (st==dr) {arb[nod].poz=st;
             arb[nod].min=gr[st];
             }
        else {
             long int mid=(st+dr)/2;
             build(nod*2,st,mid);
             build(nod*2+1,mid+1,dr);
             if (arb[nod*2].min<arb[nod*2+1].min) arb[nod]=arb[nod*2];
                                else arb[nod]=arb[nod*2+1];
             }
}

int exist(long int x, long int y)
{
lista *p;
for (p=vf[x];p;p=p->urm)
        if (p->nod==y) return 1;
return 0;
}

void muchie(long int x, long int y)
{
lista *p,*p1;
p=vf[y];
if (p->nod==x) {vf[y]=p->urm;
               delete p;}
       else {
            while (p->nod!=x)
                {
                p1=p;
                p=p->urm;
                }
             p1->urm=p->urm;
             delete p;
             }
}

void update(long int poz, long int val, long int nod, long int st, long int dr)
{
if (st==dr) arb[nod].min=val;
        else {
             long int mid=(st+dr)/2;
             if (poz<=mid) update(poz,val,nod*2,st,mid);
                else update(poz,val,nod*2+1,mid+1,dr);
             if (arb[nod*2].min<arb[nod*2+1].min) arb[nod]=arb[nod*2];
                                else arb[nod]=arb[nod*2+1];
             }
}

void scoate(long int k)
{
update(k,INF,1,1,n);
lista *p;
for (p=vf[k]; p->urm ;p=p->urm)
        {
        update(p->nod,gr[p->nod]-1,1,1,n);
        muchie(k, p->nod);
        muchie(p->nod,k);
        }
}


void solve()
{
lista *p1,*p2,*p3;
for (i=1;i<=n-2;i++)
        {
        k=arb[1].poz;
        for (p1=vf[k];p1;p1=p1->urm)
                for (p2=p1->urm;p2;p2=p2->urm)
                        if (exist(p1->nod,p2->nod)) {
                                                   clic[3]++;
                                                   for (p3=p2->urm;p3;p3=p3->urm)
                                                        if ((exist(p3->nod,p2->nod))&&(exist(p3->nod,p1->nod))) clic[4]++;
                                                    }
        scoate(k);
        }
for (i=4;!clic[i];i--);
printf("%ld %ld",i,clic[i]);
}

int main()
{
citire();
build(1,1,n);
solve();
return 0;
}