#include <stdio.h>

#include <set>
#include <queue>

using namespace std;

int n, m, nr3, nr4;
int g[30002];

set <int> v[30002];
queue <int> q;

void sol (int nod)
{
	set <int> :: iterator it1, it2, it3;
	
	for (it1 = v[nod].begin(); it1 != v[nod].end(); it1 ++)
		for (it2 = v[nod].begin(); it2 != v[nod].end(); it2 ++)
			if (*it1 < *it2 && v[*it1].find (*it2) != v[*it1].end())
			{
				nr3 ++;
				for (it3 = v[nod].begin(); it3 != v[nod].end(); it3 ++)
					if (*it2 < *it3 && v[*it1].find (*it3) != v[*it1].end() && v[*it2].find (*it3) != v[*it2].end())
						nr4 ++;
			}
}

int main ()
{
	freopen ("count.in", "r", stdin);
	freopen ("count.out", "w", stdout);
	
	scanf ("%d %d", &n, &m);
	
	int i, nod, cnod, x, y;
	
	for (i = 1; i <= m; i ++)
	{
		scanf ("%d %d", &x, &y);
		v[x].insert (y);
		v[y].insert (x);
		
		g[x] ++;
		g[y] ++;
	}
	
	for (i = 1; i <= n; i ++)
		if (g[i] <= 5)
			q.push (i);
	
	while (!q.empty())
	{
		nod = q.front();
		q.pop();
		if (g[nod] < 2)
			continue;
		
		sol(nod);
		
		for (set <int> :: iterator it = v[nod].begin(); it != v[nod].end(); it ++)
		{
			cnod = *it;
			g[cnod] --;
			v[cnod].erase (nod);
			if (g[cnod] == 5)
				q.push (cnod);
		}
	}
	
	if (!nr3)
		printf ("2 %d\n", m);
	else
		if (!nr4)
			printf ("3 %d\n", nr3);
		else
			printf ("4 %d\n", nr4);
	return 0;
}