#include <cstdio>
#include <set>
#include <deque>
#define DIMN 30010

using namespace std;
int g[DIMN],f[DIMN],used[DIMN],c[5],aux[10];
set <int> s[DIMN];
deque <int> dq;
int main()
{
    FILE *fin=fopen ("count.in","r");
    FILE *fout=fopen ("count.out","w");
    int n,m,x,y,i,nod,vecin,n1,n2,n3,elem,j,k;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&x,&y);
        g[x]++;
        g[y]++;
        s[x].insert(y);
        s[y].insert(x);
    }
    for (i=1;i<=n;i++){
        if (g[i]<6){
            dq.push_back(i);
            f[i]=1;
        }
    }
    c[1]=n;
    c[2]=m;
    while (!dq.empty()){
        nod=dq.front();
        dq.pop_front();
        used[nod]=1;
        elem=0;
        for (set <int> ::  iterator it =s[nod].begin();it!=s[nod].end();it++){
            vecin=(*it);
            if (!used[vecin])
                aux[++elem]=vecin;
        }
        for (i=1;i<elem;i++){
            for (j=i+1;j<=elem;j++){
                n1=aux[i];
                n2=aux[j];
                if (s[n1].find(n2) != s[n1].end()){
                    c[3]++;
                }
            }
        }
        for (i=1;i<elem;i++){
            for (j=i+1;j<elem;j++){
                for (k=j+1;k<=elem;k++){
                    n1=aux[i];
                    n2=aux[j];
                    n3=aux[k];
                    if (s[n1].find(n2) != s[n1].end() && s[n2].find(n3) != s[n2].end() && s[n1].find(n3) != s[n1].end()){
                        c[4]++;
                    }
                }
            }
        }
        for (set <int> ::  iterator it =s[nod].begin();it!=s[nod].end();it++){
            vecin=(*it);
            g[vecin]--;
            if (!f[vecin] && g[vecin]<6){
                f[vecin]=1;
                dq.push_back(vecin);
            }
        }
    }
    if (c[4]){
        fprintf (fout,"4 %d",c[4]);
    }
    else if (c[3]) {
        fprintf (fout,"3 %d",c[3]);
    }
    else fprintf (fout,"2 %d",m);
    return 0;
}