#include <cstdio>
#include <cstring>

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

int i,j,k,nr,max,x[60100],y[60100],m,n,frecv[10100],a,b,c,d,viz[10100],nrr;

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]);
	    scanf("%d %d", &x[i], &y[i]);
		//aa[x[i]][y[i]]=aa[y[i]][x[i]]=1;
	}
	
	
	/*for (i=1;i<=n;++i)
		 for (j=i+1;j<=n;++j)
			   for (k=j+1;k<=n;++k)
				    if (aa[i][j] && aa[i][k] && aa[j][k])
						nr++;
	
		max=3;
		
		int nrr=0;*/
	nrr=0;
	for (i=1;i<=m;++i)
         for (j=i+1;j<=m;++j)
		 {
			 a=x[i];
			 b=y[i];
			 c=x[j];
			 d=y[j];
			 
			 
			 
			 if (viz[a] && viz[b] && viz[c]) continue;
			 
			
			 memset(frecv,0,sizeof(frecv));
			 if ((a==b && a!=c && d!=c && a!=d) || (a==c && a!=b && d!=b && a!=d) || (a==d && a!=c && b!=c && a!=b) || (c==b && a!=c && d!=c && a!=d) || (d==b && a!=c && d!=c && a!=d) || (d==c && a!=c && d!=b && a!=b))
			 {
				for (k=1;k<=m;++k)
                     if ((x[k]==a || x[k]==b || x[k]==c) && 
						 (y[k]==a || y[k]==b || y[k]==c))
						 frecv[x[k]]++,
						 frecv[y[k]]++;
			 }
			 if (frecv[a]==2 && frecv[b]==2 && frecv[c]==2)
				 nrr++,
				 viz[a]=1,viz[b]=1,viz[c]=1;
			 
		 }
	if (nrr!=0)
		max=3,
		nr=nrr;
	
		memset(frecv,0,sizeof(frecv));
		nrr=0;
	for (i=1;i<=m;++i)
         for (j=i+1;j<=m;++j)
		 {
			 a=x[i];
			 b=y[i];
			 c=x[j];
			 d=y[j];
			 if (viz[a] && viz[b] && viz[c] && viz[d]) continue;
			 
			
			 memset(frecv,0,sizeof(frecv));
			 if (a!=c && b!=d && a!=d && b!=c)
			 {
				for (k=1;k<=m;++k)
                     if ((x[k]==a || x[k]==b || x[k]==c || x[k]==d) && 
						 (y[k]==a || y[k]==b || y[k]==c || y[k]==d))
						 frecv[x[k]]++,
						 frecv[y[k]]++;
			 }
			 if (frecv[a]==3 && frecv[b]==3 && frecv[c]==3 && frecv[d]==3)
				 nrr++,
				 viz[a]=1,viz[b]=1,viz[c]=1,viz[d]=1;
			 
		 }
					 
	if (nrr!=0)
		max=4,
		nr=nrr;
		 
	printf("%d %d", max,nr);
	
	fclose(stdin);
	fclose(stdout);
		
	
	return 0;
	
}