#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];

struct list
{
	int nod;
	list *link;
}*la[60005];

inline void addnod(int x,int y)
{
	list *p;
	p=new list;
	p->nod=x;
	p->link=la[y];
	la[y]=p;
	p=new list;
	p->nod=y;
	p->link=la[x];
	la[x]=p;
}

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;
	list *p;

	p=la[sol[1]];
	if(k>S) nr++;
	else
	while(p!=NULL)
	{
		if(gr[p->nod]>=S-1&&sol[k-1]<p->nod)
		{
			ok=1;
			for(j=2;j<k;j++)
				if(src(sol[j]*B+p->nod)==0)
				{
					ok=0;
					break;
				}
			if(ok)
			{
				sol[k]=p->nod;
				back(k+1);
			}
		}
		p=p->link;
	}
}
inline void solve()
{
	int i;

	for(i=x;i<=n;i++)
		if(ind[i]<=n-S+1)
		{
			sol[1]=ind[i];
			back(2);
		}
}

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);
		addnod(x,y);
		gr[x]++;
		gr[y]++;
	}
	for(i=1;i<=n;i++)
	{
		ind[i]=i;
		grr[i]=gr[i];
	}
	quicksort(1,n);

	nr=0;
	S=4;
	x=0;
	while(gr[ind[x]]<S-1) x++;
	solve();

	if(nr==0)
	{
		S=3;
		x=0;
		while(gr[ind[x]]<S-1) x++;
		solve();
		printf("%d %d\n",S,nr);
		return 0;
	}

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