#include<fstream>
#include<set>
#include<queue>
using namespace std;
ifstream f("count.in");
ofstream g("count.out");
int n,m,i,x,y,sol[5];
set<int>s[30100];
queue<int>q;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        s[x].insert(y);
        s[y].insert(x);
    }
    sol[1]=n;
    sol[2]=m;
    for(i=1;i<=n;++i)
    if(s[i].size()<6)
    q.push(i);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(set<int>::iterator it=s[x].begin();it!=s[x].end();++it)
        for(set<int>::iterator it1=it;it1!=s[x].end();++it1)
        {
            if(it==it1||s[*it].find(*it1)==s[*it].end())
            continue;
            ++sol[3];
            for(set<int>::iterator it2=it1;it2!=s[x].end();++it2)
            if(it2!=it1&&s[*it].find(*it2)!=s[*it].end()&&s[*it1].find(*it2)!=s[*it1].end())
            ++sol[4];
        }
        for(set<int>::iterator it=s[x].begin();it!=s[x].end();++it)
        {
            s[*it].erase(x);
            if(s[*it].size()<6)
            q.push(*it);
        }
        s[x].clear();
    }
    for(i=4;i;--i)
    if(sol[i])
    {
        g<<i<<' '<<sol[i]<<'\n';
        return 0;
    }
}