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

#define Nmax 30010

int n, m, i, N, K, nod, nrsol, sol, Nod, x, y, u, p, pr, fiu;
int grad[Nmax], Q[Nmax], viz[Nmax], st[8], Vv[Nmax];

set <int> A[Nmax];
vector <int> V[Nmax];

int vecini (int x, int y) {
	return A[x].find(y) != A[x].end();
}

void back (int k) {

	int i;
	if (k <= K) 
		for (i = st[k-1] + 1; i <= N; i++) {
			st[k] = i;
			back (k + 1);
		}
	
	else {
		if (K == 2)
			if ( vecini (Nod, Vv[st[1]]) && vecini (Nod, Vv[st[2]]) && vecini (Vv[st[1]], Vv[st[2]])) {
				if ( K == sol) nrsol++;
				if ( K > sol) {sol = K; nrsol = 1;}
			}
		
		if (K == 3) 
			if ( vecini (Nod, Vv[st[1]]) && vecini (Nod, Vv[st[2]]) && vecini (Vv[st[1]], Vv[st[2]]) && vecini (Vv[st[3]], Vv[st[1]]) && vecini (Vv[st[3]], Vv[st[2]]) && vecini (Nod, Vv[st[3]]) ) {
				if ( K == sol) nrsol++;
				if ( K > sol) {sol = K; nrsol = 1;}
			}
	}
	
}

void solve (int nod) {

	viz[nod] = 2; N = -1; Nod = nod;
	int i; st[0] = -1;
	
	for (i = 0; i < (int)V[nod].size(); i++) {
		fiu = V[nod][i];
		if ( viz[fiu] != 2 ) {
			Vv[++N] = fiu;
			grad[fiu]--;
			if ( grad[fiu] < 6 && viz[fiu] == 0 ){ Q[++u] = fiu; viz[fiu] = 1;}
		}
	}
	
	pr = sol; if (sol == 1) pr = 2;
	for (i = pr; i < 4 && i <= N+1; i++) 
		K = i, back (1);

}

int main () {

	FILE *f = fopen ("count.in", "r");
	FILE *g = fopen ("count.out", "w");

	fscanf (f, "%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		fscanf (f, "%d %d", &x, &y);
		V[x].push_back (y); V[y].push_back (x);
		grad[x]++, grad[y]++;
		A[x].insert (y); A[y].insert (x);
	}
	
	for (i = 1; i <= n; i++)
		if ( grad[i] < 6 )viz[i] = 1, Q[++u] = i;
	
	sol = 1; nrsol = m;
	for (p = 1; p <= u; p++) {
		solve (Q[p]);
	}
	
	fprintf (g, "%d %d", sol + 1, nrsol);
	
	fclose (f);
	fclose (g);
	
	return 0;

}