#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#define DIM (1 << 13)
#define in (read_int())
#define MAXN 30005
#define MOD 666013
#define foreach(G)  for (node *it = G; it; it = it->next)
#define hash(x, y) (x | (y << 14))

using namespace std;

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

struct node{
	int val;
	node *next;
} *List[MAXN], *Hash[MOD], *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(node *&H, int val){
	node *New = new node;
	New->next = H, New->val = val;
	H = New;
}

inline void insert_hash(int x, int y){
	int key = hash(x, y) + hash(y, x);
	
	insert(Hash[key % MOD], hash(x, y));
}

inline bool find(int x, int y){
	int key = hash(x, y) + hash(y, x),
		xy = hash(x, y), yx = hash(y, x);

	foreach(Hash[key % MOD])
		if (it->val == xy || it->val == yx) return 1;
	return 0;
}

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

	for (int i = 1; i <= nodes[0]; ++i){
		foreach(H[i]){
			for (node *it2 = it->next; it2; it2 = it2->next)
				if (find(it->val, it2->val)) 
					++Cliques[4];
			
		}
	}
	deleted[NODE] = true;
	size[NODE] = 0;
	NODE = 0;
	for (int i = 1; i <= nodes[0]; ++i)
		if (size[nodes[i]] < 6 && !deleted[nodes[i]]) { NODE = nodes[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(List[x], y), insert(List[y], x);
		++size[x], ++size[y];
		insert_hash(x, 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;
}