\#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;
}