#include<iostream>
#include<fstream>
#include<queue>
#include<set>
using namespace std;
 
ifstream in("count.in");
ofstream out("count.out");
 
int n,m,sol1,sol2;
set<int> g[30010];
queue<int> q;
 
int main() {
int i,a,b,el;
set<int>::iterator it,j,k;
 
in >> n >> m;
 
for(i=1;i<=m;++i) 
{
            in >> a >> b;
 
            g[a].insert(b);
            g[b].insert(a);
}
 
for(i=1;i<=n;++i)
if(g[i].size()<6)
q.push(i);
while(!q.empty()) 
{
            el = q.front();
            q.pop();
 
            for(it = g[el].begin(); it!=g[el].end(); ++it)
                    for(j = it; j!=g[el].end(); ++j) 
                          if(*j > *it && g[*it].count(*j) > 0) {
 
                            sol1++;
                            for(k=j; k!=g[el].end(); ++k)
                            if(*k>*j && g[*it].count(*k) > 0 && g[*j].count(*k) > 0)
                            sol2++;
            }
 
            for(it = g[el].begin(); it!=g[el].end(); ++it) {
            g[*it].erase(el);
 
            if(g[*it].size() == 5)
            q.push(*it);
            }
}
 
if(sol2)
out << "4 " << sol2 << "\n";
else
if(sol1)
out << "3 " <<  sol1 << "\n";
else
out << "2 " << m << "\n";
 
return 0;
}