#include <fstream>
#include <iostream>
#include <set>
#include <vector>
#define x first
#define y second
using namespace std;

ifstream fin("count.in");
ofstream fout("count.out");

set <int> v[30101];
set <int>::iterator it,jt;
int n,m,i,j,k,l,nod,g[30101],trei,patru;
int c[30101],p,u;
bool f[30101];
vector <int> aux;

int main(){
    fin>>n>>m;
    for(k=1;k<=m;k++){
        fin>>i>>j;

        v[i].insert(j);
        v[j].insert(i);
        g[i]++; g[j]++;
    }

    p=1;
    for(i=1;i<=n;i++)
        if(g[i]<=5)
            c[++u]=i,f[i]=1;

    while(p<=u){
        nod=c[p];

        for(it=v[nod].begin();it!=v[nod].end();it++)
            aux.push_back(*it);
        l=aux.size();

        ///trei
        for(i=0;i<l-1;i++)
            for(j=i+1;j<l;j++)
                if(v[aux[i]].find(aux[j])!=v[aux[i]].end())
                    trei++;//,cout<<nod<<" "<<aux[i]<<" "<<aux[j]<<"\n";

        ///patru
        for(i=0;i<l-2;i++)
            for(j=i+1;j<l-1;j++)
                for(k=j+1;k<l;k++)
                    if( v[aux[i]].find(aux[j])!=v[aux[i]].end() && v[aux[i]].find(aux[k])!=v[aux[i]].end() && v[aux[j]].find(aux[k])!=v[aux[j]].end() )
                        patru++;

        for(i=0;i<l;i++){
            v[nod].erase( aux[i] );
            v[ aux[i] ].erase(v[aux[i]].find(nod));
            g[ aux[i] ]--;
            g[nod]--;

            if(g[aux[i]]<=5 && f[aux[i]]!=0){
                f[aux[i]]=1;
                c[++u]=aux[i];
            }
        }
        aux.clear();

        p++;
    }

    if(patru){
        fout<<4<<" "<<patru;
        return 0;
    }

    if(trei){
        fout<<3<<" "<<trei;
        return 0;
    }

    fout<<2<<" "<<m;

    return 0;
}