#include <cstdio>
#include <vector>

using namespace std;

#define Nmax 30005

#define pb(v, a) v.push_back(a)
#define popb(v) v.pop_back()
#define sz(a) a.size()

vector< vector<int> > vec;
int n, gr[Nmax], Q[Nmax], viz[Nmax], number[5], inq[Nmax];

void readdata()
{
	freopen("count.in", "r", stdin);
	freopen("count.out", "w", stdout);
	
	int m, a, b;
	
	scanf("%d %d", &n, &m);
	vec.resize(n+1);
	
	for (; m; --m)
	{
		scanf("%d %d", &a, &b);
		pb(vec[a], b);
		pb(vec[b], a);
		++gr[a]; ++gr[b];
	}
}

int muchie(int a, int b)
{
	int i, lim = sz(vec[a]);
	for (i = 0; i < lim; ++i)
		if (vec[a][i] == b) return 1;
	return 0;
}

int clica(int nod, int conf, int nr)
{
	int i, j;
	vector<int> v;
	
	for (i = 0; i < nr; ++i)
		if ((conf >> i) % 2 == 1) pb(v, vec[nod][i]);
	for (i = 0; i < sz(v); ++i)
		for (j = i+1; j < sz(v); ++j)
			if (muchie(v[i], v[j]) == 0) return 0;
	return 1;
}

void scoate(int a, int b)
{
	int i, lim = sz(vec[a]);
	for (i = 0; i < lim; ++i)
	if (vec[a][i] == b)
	{
		vec[a][i] = vec[a][lim-1];
		popb(vec[a]);
	}
}

void solve()
{
	int i, cont = 0, cap = 1, nr, cnt, nod, aux;
	
	for (i = 1; i <= n; ++i)
		if (gr[i] < 6)
		{
			Q[++cont] = i;
			inq[i] = 1;
		}
	while (cap <= cont)
	{
		nod = Q[cap];
		nr = sz(vec[nod]);
		for (i = 1; i <= (1 << nr)-1; ++i)
		{
			aux = i;
			cnt = 1;
			while (aux)
			{
				if (aux % 2 == 1) ++cnt;
				aux /= 2;
			}
			if (clica(nod, i, nr))
				++number[cnt];
		}
		for (i = 0; i < nr; ++i)
		{
			scoate(vec[nod][i], nod);
			--gr[vec[nod][i]];
			if ((gr[vec[nod][i]] < 6) && (!inq[vec[nod][i]]))
			{
				Q[++cont] = vec[nod][i];
				inq[vec[nod][i]] = 1;
			}
		}
		++cap;
	}
	for (i = 4; i; --i)
	if (number[i])
	{
		printf("%d %d\n", i, number[i]);
		return;
	}
}

int main()
{
	readdata();
	solve();
	return 0;
}