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