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

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

long int i,j,k,n,m,gr[NMAX],x,y;
long int clic[5];
long int queue[NMAX],st,dr;
char s[20];


void citire()
{
freopen("count.in","rt",stdin);
freopen("count.out","wt",stdout);
scanf("%ld %ld\n",&n,&m);
clic[1]=n;
clic[2]=m;
lista *p;
for (i=1;i<=m;i++)
        {
        fgets(s,20,stdin);
        sscanf(s,"%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;
        }
}

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];
gr[y]--;
if (gr[y]==5) queue[++dr]=y;
if (p->nod==x) {vf[y]=p->urm;
               p=NULL;}
       else {
            while (p->nod!=x)
                {
                p1=p;
                p=p->urm;
                }
             p1->urm=p->urm;
             delete p;
             }
}

void scoate(long int k)
{
lista *p;
p=vf[k];
while (p)
        {
        muchie(k, p->nod);
        p=p->urm;
        }
}


void solve()
{
lista *p1,*p2,*p3;
for (i=1;i<=n-2;i++)
        {
        k=queue[st++];
        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();
st=1;dr=0;
for (i=1;i<=n;i++)
        if (gr[i]<6) queue[++dr]=i;
solve();
return 0;
}