#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <queue>
#define MAXN 30050

using namespace std;

int n, m, cate;
unordered_map<int, int> graf[MAXN];
unordered_map<int, int> cop[MAXN];
queue<int> smal;

void citire()
{
	int x, y;
	scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
		scanf("%d %d", &x, &y);
        graf[x].insert(make_pair(y, 1));
        graf[y].insert(make_pair(x, 1));
    }
    for (int i = 1; i <= n; i++)
		cop[i] = graf[i];
}

int v[10], sol[10], nq, top;
int er[MAXN], lvl;

void backt(int k, int sz)
{
	if (k == sz) {
        cate++;
        for (int i = 1; i < k; i++) {
			int vec = v[sol[i]];
			graf[vec].erase(top);
            if (graf[vec].size() < 6 && !er[vec]) {
				smal.push(vec);
				er[vec] = 1;
            }
        }
		return;
	}
	for (int i = sol[k-1]+1; i <= nq; i++) {
		int ok = 1;
        for (int j = 1; ok && j < k; j++)
			if (graf[v[sol[j]]].count(v[i]) == 0)
				ok = 0;
		if (ok) {
			sol[k] = i;
			backt(k+1, sz);
		}
	}
}

void solve(int sz)
{
	while (!smal.empty()) smal.pop();
	for (int i = 1; i <= n; i++) er[i] = 0;
	for (int i = 1; i <= n; i++)
		if (graf[i].size() < 6) {
			smal.push(i);
			er[i] = 1;
		}
    while (!smal.empty()) {
        top = smal.front();
        smal.pop();
        nq = 0;
        for (auto it = graf[top].begin(); it != graf[top].end(); ++it)
			v[++nq] = it->first;
        backt(1, sz);
    }
}

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

	citire();
	solve(4), lvl = 4;
	if (cate == 0) {
		while (true);
		for (int i = 1; i <= n; i++)
			graf[i] = cop[i];
		solve(3), lvl = 3;
	}
	if (cate == 0)
		cate = m, lvl = 2;
	printf("%d %d", lvl, cate);

    return 0;
}