#include <stdio.h>
#include <set>

using namespace std;

#define maxn 30010

int n,m,l;
int sol,rez;
set <int> a[maxn];
set <int> :: iterator I,J,K;
int c[maxn],s[maxn],u[maxn];

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

	scanf("%d %d ",&n,&m);

	int i,x,y;

	for (i=1;i<=m;i++)
	{
		scanf("%d %d ",&x,&y);

		a[x].insert(y);
		a[y].insert(x);
		c[x]++, c[y]++;
	}

	for (i=1;i<=n;i++)
		if (c[i] < 6)
		{
			s[++l] = i;
			u[i] = 1;
		}

	sol = 2;
	rez = m;

	for (i=1;i<=l;i++)
	{
		for (I = a[s[i]].begin(); I!=a[s[i]].end(); ++I)
		{
			c[*I]--;
			if (!u[*I] && c[*I]<6) s[++l] = *I;
		}

		for (I = a[s[i]].begin(); I!=a[s[i]].end(); ++I)
			for (J = I, J++; J!=a[s[i]].end(); ++J)
				if (a[*I].find(*J) != a[*I].end())
				{
					if (sol < 3)
					{
						sol = 3;
						rez = 1;
					}
					else if (sol == 3) rez++;

					for (K = J, K++; K!=a[s[i]].end(); ++K) 
					{
						if (a[*I].find(*K) != a[*I].end() && a[*J].find(*K) != a[*J].end())
						{
							if (sol < 4)
							{
								sol = 4;
								rez = 0;
							}
							rez++;
						}
					}
				}		
		for (I = a[s[i]].begin(); I != a[s[i]].end(); I++) a[*I].erase(s[i]);
		a[s[i]].clear();
	}

	printf("%d %d\n",sol,rez);

	return 0;
}