#include<fstream>
#include<algorithm>
#include<bitset>
#include<set>
#include<queue>
using namespace std;
ifstream fin("count.in");
ofstream fout("count.out");
queue <int> q;
set <int> L[30005];
bitset <30005> ap,a;
int n,m,x,y,p,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 && !p;++i)
        if (L[i].size()<6)
            q.push(i);
    while (!q.empty())
    {
        p=q.front();
        st[1]=p, ap[p]=1;
        back(2);
        for (it=L[p].begin();it!=L[p].end();++it)
        {
            L[*it].erase(p);
            if (L[*it].size()<6)
            {
                if (!a[*it])
                    q.push(*it);
            }
        }
        ap[p]=0, a[p]=1;
        q.pop();
    }
    sol[3]/=2, sol[4]/=6;
    for (i=4;i>0;--i)
        if (sol[i])
        {
            fout<<i<<" "<<sol[i]<<"\n";
            break;
        }
    return 0;
}