#include <fstream>
#include <iostream>
#include <unordered_set>
#include <vector>
#include <queue>
using namespace std;

long long count_k4s(const vector<unordered_set<int> >& v, const int x){
	long long rez = 0;
	for(const auto a : v[x]){
		for(const auto b : v[x]){
			for(const auto c : v[x]){
				if(v[a].find(b) != end(v[a]) &&
					v[b].find(c) != end(v[b]) &&
					v[c].find(a) != end(v[c])){
					++rez; } } } }
	return rez; }

long long count_k3s(const vector<unordered_set<int> >& v, const int x){
	long long rez = 0;
	for(const auto a : v[x]){
		for(const auto b : v[x]){
			if(v[a].find(b) != end(v[a])){
				++rez; } } }
	return rez; }

int main(){
	ifstream f("count.in");
	ofstream g("count.out");
	int n, m;
	f >> n >> m;
	vector<unordered_set<int> > v(n);
	for(int i = 0, a, b; i < m; ++i){
		f >> a >> b;
		--a, --b;
		v[a].insert(b);
		v[b].insert(a); }
	queue<int> de_viz;	
	for(int i = 0; i < n; ++i){
		if(v[i].size() < 6){
			de_viz.push(i); } }
	vector<bool> facut(n, false);
	long long nr_k3s = 0, nr_k4s = 0;
	while(!de_viz.empty()){
		const int cur = de_viz.front();
		de_viz.pop();
		if(!facut[cur]){
			facut[cur] = true;
			if(nr_k4s == 0){
				nr_k3s += count_k3s(v, cur); }
			nr_k4s += count_k4s(v, cur);
			for(const auto other : v[cur]){
				v[other].erase(cur);
				if(v[other].size() < 6){
					de_viz.push(other); } }
			v[cur].clear(); } }
	if(nr_k4s > 0){
		g << 4 << ' ' << (nr_k4s/6); }
	else if(nr_k3s > 0){
		g << 3 << ' ' << (nr_k3s/2); }
	else if(m > 0){
		g << 2 << ' ' << m; }
	else{
		g << 1 << ' ' << n; }
	return 0; }