#include <bits/stdc++.h>
using namespace std;
ifstream f ("count.in");
ofstream g ("count.out");
const int nmax=1e4+3;
int grad[nmax],viz[nmax],used[nmax],sol[5],pwp[10],n,m,x,y,nod,urm,t1,t2,t3,nr;
set <int> s[nmax];
deque <int>
usu;
int main()
{
    ios::sync_with_stdio(false);
    cout.tie(0);
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y;
        ++grad[x];
        ++grad[y];
        s[x].insert(y);
        s[y].insert(x);
    }
    for(int i=1;i<=n;++i)
    {
        if(grad[i]<=5)
        {
            usu.push_back(i);
            viz[i]=1;
        }
    }
    sol[1]=n;
    sol[2]=m;
    while(!usu.empty())
    {
        nod=usu.front();
        usu.pop_front();
        used[nod]=1;
        nr=0;
        for(set <int>:: iterator it=s[nod].begin();it!=s[nod].end();++it)
        {
            urm=(*it);
            if(!used[urm]) pwp[++nr]=urm;
        }
        for(int i=1;i<nr;++i)
        {
            for(int j=i+1;j<=nr;++j)
            {
                t1=pwp[i];
                t2=pwp[j];
                if(s[t1].find(t2)!=s[t1].end()) ++sol[3];
            }
        }
        for(int i=1;i<nr;++i)
        {
            for(int j=i+1;j<nr;++j)
            {
                for(int k=j+1;k<=nr;++k)
                {
                    t1=pwp[i];
                    t2=pwp[j];
                    t3=pwp[k];
                    if(s[t1].find(t2)!=s[t1].end()&&s[t2].find(t3)!=s[t2].end()&&s[t1].find(t3)!=s[t1].end()) ++sol[4];
                }
            }
        }
        for(set <int>:: iterator it=s[nod].begin();it!=s[nod].end();++it)
        {
            urm=(*it);
            --grad[urm];
            if(!viz[urm]&&grad[urm]<=5)
            {
                viz[urm]=1;
                usu.push_back(urm);
            }
        }
    }
    if(sol[4]) g<<4<<' '<<sol[4];
    else if(sol[3]) g<<3<<' '<<sol[3];
    else g<<2<<' '<<m;
    return 0;
}