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