#include <bits/stdc++.h>
using namespace std;
ifstream in("count.in");
ofstream out("count.out");
const int lim=3e4+5;
set<int> vec[lim];
queue<int> q;
bool inq[lim];
int main()
{
    int n,m,x,y;
    in>>n>>m;
    for(int i=1;i<=m;++i)
    {
        in>>x>>y;
        vec[x].insert(y);
        vec[y].insert(x);
    }
    for(int i=1;i<=n;++i)
    if(vec[i].size()<6)
    {
        q.push(i);
        inq[i]=true;
    }
    int ans3,ans4;
    ans3=ans4=0;
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        for(set<int>::iterator it1=vec[x].begin();it1!=vec[x].end();++it1)
        for(set<int>::iterator it2=it1;it2!=vec[x].end();++it2) if(vec[*it1].find(*it2)!=vec[*it1].end()) ++ans3;

        for(set<int>::iterator it1=vec[x].begin();it1!=vec[x].end();++it1)
        for(set<int>::iterator it2=it1;it2!=vec[x].end();++it2) if(vec[*it1].find(*it2)!=vec[*it1].end())
        for(set<int>::iterator it3=it2;it3!=vec[x].end();++it3) if(vec[*it1].find(*it3)!=vec[*it1].end() and
                                                                vec[*it2].find(*it3)!=vec[*it2].end()) ++ans4;
        for(set<int>::iterator it=vec[x].begin();it!=vec[x].end();++it)
        {
            vec[*it].erase(vec[*it].find(x));
            if(vec[*it].size()<6 and inq[*it]==false) inq[*it]=true,q.push(*it);
        }
    }
    if(ans4) out<<4<<' '<<ans4<<'\n';
    else if(ans3) out<<3<<' '<<ans3<<'\n';
    else out<<2<<' '<<m<<'\n';
    return 0;
}