#include <cstdio>
#include <map>
#include <vector>
#define maxn 30010

using namespace std;

int n, m, i, j, a, b;
int grad[maxn];
map <int, int> g[maxn];
vector <int> v[maxn];
int sol[5];
bool viz[maxn];

inline void solve(int nod, int nr, int z[]) {
	int i, j, k, ok, t[10], p = 0;
	
	for (i = 1; i <= (1 << nr); i++) {
		p = 0; 
		for (j = 0; j < nr; j++)
			if (i & (1 << j)) {
				p++;
				t[p] = z[j + 1];
			}
		p++;
		t[p] = nod;
		
		ok = 1;
		for (j = 1; j <= p; j++)
			for (k = j + 1; k <= p; k++)
				if (g[t[j]][t[k]] == 0) {
					ok = 0;
					j = p + 1; k = p + 1;
					break;
				}
				
		if (ok)	sol[p]++;
	
	}
}

void df(int nod) {
	if (viz[nod])
		return;
	viz[nod] = 1;
	
	int i, fiu;
	int z[6], nr = 0;
	
	for (i = 0; i < v[nod].size(); i++) {
		fiu = v[nod][i];
		if (g[nod][fiu] == 1 && viz[fiu] == 0) {
			nr++;
			z[nr] = fiu;
		}
	}
	
	solve(nod, nr, z);
	
	for (i = 1; i <= nr; i++) {
		g[z[i]][nod] = 0;
		g[nod][z[i]] = 0;
		grad[z[i]]--;
		if (grad[z[i]] < 6)
			df(z[i]);
	}
	
}

int main() {
	freopen("count.in", "r", stdin);
	freopen("count.out", "w", stdout);
	
	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf("%d%d", &a, &b);
		g[a][b] = 1;
		g[b][a] = 1;
		grad[a]++; grad[b]++;
		v[a].push_back(b); v[b].push_back(a);
	}
	
	for (i = 1; i <= n; i++)
		if (!viz[i])
			if (grad[i] <= 5)
				df(i);
	
	for (i = 4; i > 0; i--) 
		if (sol[i]) {
			printf("%d %d\n", i, sol[i]);
			return 0;
		}			
	
			
	return 0;
}