#include<bits/stdc++.h>
#define maxN 30005
using namespace std;
int n,m,x,y,cnt[6],gr[maxN];
deque<int> q;
unordered_set<int> v[maxN];
int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        v[x].insert(y);
        v[y].insert(x);
        gr[x]++;
        gr[y]++;
    }
 
    for(int i=1;i<=n;i++)
    {
        if(gr[i]<6) q.push_back(i);
    }
    cnt[1]=n;
    cnt[2]=m;
    while(!q.empty())
    {
        int nod=q.front();
        q.pop_front();
 
        for(unordered_set<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
            for(unordered_set<int>::iterator it1=it;it1!=v[nod].end();it1++)
                if(v[*it].find(*it1)!=v[*it].end()) cnt[3]++;
 
        for(unordered_set<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
            for(unordered_set<int>::iterator it1=it;it1!=v[nod].end();it1++)
                for(unordered_set<int>::iterator it2=it1;it2!=v[nod].end();it2++)
                    if(v[*it].find(*it1)!=v[*it].end() && v[*it].find(*it2)!=v[*it].end() && v[*it1].find(*it2)!=v[*it1].end()) cnt[4]++;
 
        for(unordered_set<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
        {
            int vec=*it;
            v[vec].erase(v[vec].find(nod));
            gr[vec]--;
            if(gr[vec]==5) q.push_back(vec);
        }
    }
    for(int i=4;i>=1;i--)
        if(cnt[i])
        {
            printf("%d %d\n",i,cnt[i]);
            break;
        }
    return 0;
}