#include <fstream>
#include <set>
#include <queue>
#define DIM 30005
#define sint set<int>::iterator
#define infile "count.in"
#define outfile "count.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

set<int> L[DIM];

queue<int> Q;

int Degree[DIM];
int SOL[6]; //in SOL[i]: nr de clici cu i noduri

int n, m, x, y;

int main() {
	f >> n >> m;
	for (int i = 1; i <= m; ++i) {
		f >> x >> y;
		L[x].insert(y);
		L[y].insert(x);
		++Degree[x];
		++Degree[y];
	}
	for (int i = 1; i <= n; ++i)
		if (Degree[i] < 6)
			Q.push(i);
	SOL[1] = n;    //clici cu un nod
	SOL[2] = m;    //clici cu doua noduri
	while (!Q.empty()) {
		int nod = Q.front();
		Q.pop();
		for (sint it1 = L[nod].begin(); it1 != L[nod].end(); ++it1) {
			for (sint it2 = it1; it2 != L[nod].end(); ++it2) {
				if (it1 == it2 || L[*it1].find(*it2) == L[*it1].end())
					continue;
				++SOL[3];
				for (sint it3 = it2; it3 != L[nod].end(); ++it3) {
					if (it2 == it3 || L[*it1].find(*it3) == L[*it1].end() || L[*it2].find(*it3) == L[*it2].end())
						continue;
					++SOL[4];
				}
			}
		}
		for (sint it = L[nod].begin(); it != L[nod].end(); ++it) {
			--Degree[*it];
			if (Degree[*it] == 5)
				Q.push(*it);
			L[*it].erase(nod);
		}
	}
	for (int i = 4; i; --i) {
		if (SOL[i]) {
			g << i << " " << SOL[i];
			return 0;
		}
	}
	return 0;
}

//Trust me, I'm the Doctor!