#include <cstdio>
#include <cassert>
#include <vector>
#include <set>
using namespace std;

const int NMAX = 30010;

int n,m;
vector<int> G[NMAX];
int grad[NMAX];
set< pair<int,int> > M;
bool check[NMAX];
int nrc[5];

vector<int> &v = G[0]; // initializat doar ca sa compileze
vector<bool> used;
int st[3];

bool clica ( int k ) {
	for (int i = 0; i < k; ++i)
		for (int j = i+1; j <= k; ++j)
			if (M.find(make_pair(v[st[i]],v[st[j]])) == M.end())
				return false;
	return true;
}

void back ( int k ) {
	for (st[k] = (k == 0) ? 0 : st[k-1]+1; st[k] < v.size(); ++st[k]) {
		if (!used[st[k]]) {
			used[st[k]] = true;
			if (clica(k)) ++nrc[k+2];
			if (k < 2) back(k+1);
			used[st[k]] = false;
		}
	}
}

void go ( int k ) {
	check[k] = true;
	v = G[k];
	used.resize(v.size());
	for (int i = 0; i < v.size(); ++i) used[i] = check[v[i]];
	back(0);
	for (int i = 0; i < v.size(); ++i) --grad[v[i]];
	for (int i = 0; i < v.size(); ++i)
		if (grad[v[i]] < 6 && !check[v[i]])
			go(v[i]);
}

int main() {
	freopen("count.in","rt",stdin);
	freopen("count.out","wt",stdout);
	
	scanf("%d %d",&n,&m);
	for (int i = 0; i < m; ++i) {
		pair<int,int> p;
		scanf("%d %d",&p.first,&p.second);
		--p.first; --p.second;
		if (M.find(p) == M.end()) {
			M.insert(p);
			G[p.first].push_back(p.second);
			p.first ^= p.second ^= p.first ^= p.second;
			M.insert(p);
			G[p.first].push_back(p.second);
		}
	}
	for (int i = 0; i < n; ++i) grad[i] = G[i].size();

	for (int i = 0; i < n; ++i)
		if (!check[i] && grad[i] < 6)
			go(i);
	for (int i = 0; i < n; ++i) assert(check[i]);

	if (nrc[4] > 0)
		printf("4 %d\n",nrc[4]); else
	if (nrc[3] > 0)
		printf("3 %d\n",nrc[3]); else
		printf("2 %d\n",nrc[2]);
	return 0;
}