#include <cstdio>
#include <set>
#include <queue>

using namespace std;

set<int> v[30010];
queue<int> q;
int sol[5];

int main()
{
    freopen("count.in", "r", stdin);
    freopen("count.out", "w", stdout);
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    sol[1]=n;sol[2]=m;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        v[x].insert(y);
        v[y].insert(x);
    }
    for(int i=1;i<=n;i++) if(v[i].size()<6) q.push(i);
    while(!q.empty())
    {
        int nod=q.front();q.pop();
        for(set<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
            for(set<int>::iterator it1=it;it1!=v[nod].end();it1++)
                if(*it!=*it1 && v[*it].find(*it1)!=v[*it].end())
                {
                    sol[3]++;
                    for(set<int>::iterator it2=it1;it2!=v[nod].end();it2++)
                        if(*it2!=*it && v[*it].find(*it2)!=v[*it].end() && v[*it1].find(*it2)!=v[*it1].end()) sol[4]++;
                }
        for(set<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
        {
            v[*it].erase(nod);
            if(v[*it].size()==5) q.push(*it);
        }
    }
    for(int i=4;i;i--)
        if(sol[i]) {printf("%d %d",i,sol[i]);break;}
    return 0;
}