#include <stdio.h>

int n,m,S,i,gr[30005],x,y,nr,sol[30005],B,M=999983,ind[30005],grr[30005];

struct hash
{
	int nod;
	hash *link;
}*H[1000000];
inline void add(int x)
{
	hash *p;
	p=new hash;
	p->nod=x;
	p->link=H[x%M];
	H[x%M]=p;
}

inline int src(int x)
{
	hash *p;
	p=H[x%M];
	while(p!=NULL)
	{
		if(p->nod==x) return 1;
		p=p->link;
	}
	return 0;
}

inline void back(int k)
{
	int i,j,ok;

	if(k>S) nr++;
	else
		for(i=1;i<=n;i++)
			if(gr[ind[i]]>=S-1&&sol[k-1]<ind[i])
			{
				ok=1;
				for(j=1;j<k;j++)
					if(src(sol[j]*B+ind[i])==0)
					{
						ok=0;
						break;
					}
				if(ok)
				{
					sol[k]=ind[i];
					back(k+1);
				}
			}
}

inline void quicksort(int L,int R)
{
	int i=L,j=R,aux,piv=grr[(L+R)/2];
	while(i<=j)
	{
		while(piv<grr[j]) j--;
		while(grr[i]<piv) i++;
		if(i<=j)
		{
			aux=grr[i];
			grr[i]=grr[j];
			grr[j]=aux;
			aux=ind[i];
			ind[i]=ind[j];
			ind[j]=aux;
			i++;
			j--;
		}
	}

	if(i<R) quicksort(i,R);
	if(L<j) quicksort(L,j);
}

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

	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++) gr[i]=0;
	B=n+1;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		add(x*B+y);
		add(y*B+x);
		gr[x]++;
		gr[y]++;
	}
	for(i=1;i<=n;i++)
	{
		ind[i]=i;
		grr[i]=gr[i];
	}
	quicksort(1,n);

	nr=0;
	sol[0]=0;
	S=4;
	back(1);

	if(nr==0)
	{
		S=3;
		back(1);
		printf("%d %d\n",S,nr);
		return 0;
	}

	printf("%d %d\n",S,nr);
	return 0;
}