#include<fstream>
#include<algorithm>
#include<bitset>
#include<set>
using namespace std;
ifstream fin("count.in");
ofstream fout("count.out");
set <int> q,L[30005];
bitset <30005> ap;
int n,m,x,y,p,aux,st[8],sol[8];
void back(int k)
{
    int i,ok;
    set <int>::iterator it;
    for (it=L[st[k-1]].begin();it!=L[st[k-1]].end();++it)
        if (!ap[*it])
        {
            st[k]=*it, ap[*it]=1;
            for (i=1,ok=1;i<k;++i)
                if (L[*it].find(st[i])==L[*it].end())
                {
                    ok=0;
                    break;
                }
            if (ok)
            {
                ++sol[k];
                if (k<4) back(k+1);
            }
            ap[*it]=0;
        }
}
int main()
{
    int i;
    set <int>::iterator it;
    fin>>n>>m;
    for (i=1;i<=m;++i)
    {
        fin>>x>>y;
        L[x].insert(y);
        L[y].insert(x);
    }
    for (i=1;i<=n;++i)
        q.insert(i);
    for (i=1;i<=n && !p;++i)
        if (L[i].size()<6)
            p=i;
    q.erase(p);
    while (!q.empty())
    {
        st[1]=p, ap[p]=1;
        back(2);
        aux=0;
        for (it=L[p].begin();it!=L[p].end();++it)
        {
            L[*it].erase(p);
            if (L[*it].size()<6 && !aux)
                aux=*it;
        }
        ap[p]=0;
        if (!q.empty())
            q.erase(p);
        if (!aux)
            for (it=q.begin();it!=q.end() && !aux;++it)
                if (L[*it].size()<6 && !aux)
                    aux=*it;
        p=aux;
    }
    sol[3]/=2, sol[4]/=6;
    for (i=4;i>0;--i)
        if (sol[i])
        {
            fout<<i<<" "<<sol[i]<<"\n";
            break;
        }
    return 0;
}