#include <iostream>
#include <fstream>
#include <queue>
#include <set>
using namespace std;
ifstream si("count.in");
ofstream so("count.out");
int s[5],f[30005];
queue<short> q;
set<short> g[30005];
bool ok(int a,int b)
{
    return a!=b&&g[a].find(b)!=g[a].end();
}
int main()
{
    int n,m;
    si>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        si>>x>>y;
        g[x].insert(y);
        g[y].insert(x);
        f[x]++;
        f[y]++;
    }
    for(int i=1;i<=n;++i)
        if(f[i]<6)
            q.push(i);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        set<short>::iterator i,j,k,sf;
        for(i=g[x].begin(),sf=g[x].end();i!=sf;++i)
            for(j=i;j!=sf;++j)
                if(ok(*i,*j))
                    for(k=j,s[3]++;k!=sf;++k)
                        s[4]+=(ok(*i,*k)&&ok(*j,*k));
        for(i=g[x].begin();i!=sf;++i)
        {
            g[*i].erase(x);
            if(--f[*i]==5)
                q.push(*i);
        }
    }
    s[2]=m;
    for(int i=4;i;--i)
        if(s[i])
        {
            so<<i<<' '<<s[i]<<'\n';
            break;
        }
    return 0;
}