#include <stdio.h>
#include <algorithm>
using namespace std;

const int DIM = 60005;
struct muc { int a; int b; } L[DIM<<1];
int N, M, P[DIM>>1], NR;

int cmp (muc a, muc b)
{
	if (a.a != b.a)
		return a.a < b.a;
	return a.b < b.b;
}

int dif (int i, int j)
{
	int a = L[i].a, b = L[i].b, c = L[j].a, d = L[j].b; 
	return a != c && a != d && b != c && b != d;	
}

int cauta (int a, int b)
{
	int p = P[a], u = P[a+1]-1, m;
	while (p <= u)
	{
		m = (p + u) >> 1;
		if (L[m].b == b)
			return 1;
		if (L[m].b < b)
			p = m + 1;
		else
			u = m - 1;		
	}
	return 0;
}

void clica3 ()
{
	int i, j;
	for (i = 0; i < 2*M; i++)
		for (j = i+1; L[i].a == L[j].a; j++)
			NR += cauta (L[i].b, L[j].b);
}

void clica4 ()
{
	int i, j, a, b, c, d;
	for (i = 0; i < 2*M; i++)
		for (j = 0; j < 2*M; j++)
			if ( dif(i, j) )
			{
				a = L[i].a, b = L[i].b, c = L[j].a, d = L[j].b;
				NR += cauta (a, c) && cauta (a, d) && cauta (b, c) && cauta (b, d);
			}
}

int main ()
{
	freopen ("count.in", "r", stdin);
	freopen ("count.out", "w", stdout);
	
	scanf ("%d%d", &N, &M);
	for (int i = 0; i < 2*M; i += 2)
	{
		scanf ("%d%d", &L[i].a, &L[i].b);
		L[i+1].a = L[i].b;
		L[i+1].b = L[i].a;
	}
	sort (L, L + 2*M, cmp);
	for (int i = 0; i < 2*M; i++)
		if ( !P[L[i].a] )
			P[L[i].a] = i;
	P[N+1] = 2*M;
	for (int i = N; i >= 1; i--)
		if ( !P[i] )
			P[i] = P[i+1];
	P[1] = 0;
	
	clica4 ();
	if (NR)
		printf ("4 %d\n", NR/24);
	else
	{
		clica3 ();
		if (NR)
			printf ("3 %d\n", NR/3);
		else
			printf ("3 %d\n", M);
	}

	
	return 0;
}