#include <stdio.h>

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

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;

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

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]++;
	}

	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;
}