#include <cstdio>
#include <cstring>

#define file_in "count.in"
#define file_out "count.out"

int x[41000],y[41000],nr,p[1010],max,nrmax,n,m;

void back(int k, int mm)
{
	int i;
	if (k==mm+1)
	{
		int j,k;
		//solve
		int okk=0;
		for (j=1;j<mm && !okk;++j)
		{
			int ok=0;
			for (k=1;k<=m && !ok;++k)
				if ((x[k]==p[j] && y[k]==p[j+1]) || (x[k]==p[j+1] && y[k]==p[j]))
					//  ok=0;
				  ///else
					  ok=1;
			if (!ok) okk=1;
		}
		int ok=0;
		for (k=1;k<=m && !ok;++k)
			if ((x[k]==p[1] && y[k]==p[mm]) || (x[k]==p[mm] && y[k]==p[1]))
				ok=1;
		
		if (okk==0 && ok) nr++;
		/*for (int j=1;j<=mm;++j)
			 printf("%d ", p[j]);
		printf("\n");*/
	}
	else
		for (i=p[k-1]+1;i<=n-mm+k;++i)
        {
			p[k]=i;
			back(k+1,mm);
		}
}
 
int main()
{
	int i;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &m);
	
	for (i=1;i<=m;++i)
		 scanf("%d %d", &x[i], &y[i]);
	
	for (i=2;i<=4;++i)
	{
		nr=0;
		memset(p,0,sizeof(p));
		back(1,i);
		if (i>max && nr!=0) 
		{
			max=i;
			nrmax=nr;
		}
	}
	
	printf("%d %d", max,nrmax);
	
	fclose(stdin);
	fclose(stdout);
		
	
	return 0;
	
}