#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#define DIM (1 << 13)
#define in (read_int())
#define MAXN 30005
#define foreach(G)  for (hash_line *it = G; it; it = it->next)

using namespace std;

int bpos = DIM, N, M, size[MAXN], Cliques[5], NODE, len;
char buf[DIM];
bool deleted[MAXN];

struct hash_line{
	int val;
	hash_line *next;
} *Hash[MAXN], *H[6], *Q2;

inline int read_int(){
	while (buf[bpos] < '0' || buf[bpos] > '9'){
		++bpos;
		if (bpos >= DIM) len = (int)fread(buf, 1, DIM, stdin), bpos = 0;
	}

	int val = 0;
	while (buf[bpos] <= '9' && buf[bpos] >= '0'){
		if (bpos == len) break;
		val = val * 10 + buf[bpos] - '0';
		if (++bpos == DIM) len = (int)fread(buf, 1, DIM, stdin), bpos = 0;
	}
	return val;
}

inline void insert(hash_line *&H, int val){
	hash_line *New = new hash_line;
	New->next = H, New->val = val;
	H = New;
}

inline bool find(hash_line *&H, int val){
	foreach(H) if (it->val == val) return true;
	return false;
}

void count(int baseN){
	int node[6];
	hash_line *del;
	node[0] = 0;
	for (int i = 1; i <= 5; ++i){
		del = NULL;
		foreach(H[i])
			delete del, del = it;
		delete del;
		H[i] = NULL;
	}
	
	foreach(Hash[baseN])
		if (!deleted[it->val]) node[++node[0]] = it->val,
			--size[it->val];
	
	for (int i = 1; i < node[0]; ++i)
		for (int j = node[0]; j > i; --j)
			if (find(Hash[node[i]], node[j])) 
				++Cliques[3], insert(H[i], node[j]);

	for (int i = 1; i <= node[0]; ++i){
		foreach(H[i]){
			for (hash_line *it2 = it->next; it2; it2 = it2->next)
				if (find(Hash[it->val], it2->val)) 
					++Cliques[4];
			
		}
	}
	deleted[NODE] = true;
	size[NODE] = 0;
	NODE = 0;
	for (int i = 1; i <= node[0]; ++i)
		if (size[node[i]] < 6 && !deleted[node[i]]) { NODE = node[i]; break; }
	if (size[NODE]) count(NODE);
}

int main(){
	freopen("count.in", "r", stdin);
	freopen("count.out", "w", stdout);

	N = in, M = in;
	for (int i = 0; i < M; ++i){
		int x = in, y = in;
		insert(Hash[x], y), insert(Hash[y], x);
		++size[x], ++size[y];
	}
	for (int i = 1; i <= N; ++i)
		if (size[i] < 6 && size[i] && !deleted[i]){
			NODE = i;
			count(NODE);
		}

	if (Cliques[4]) printf("4 %d\n", Cliques[4]);
	else if (Cliques[3]) printf("3 %d\n", Cliques[3]);
	else printf("2 %d\n", M);

	return 0;
}