#include <stdio.h>
#include <bitset>
#include <vector>
#define NMax 30010
using namespace std;

const char IN[]="count.in",OUT[]="count.out";

int N,M;
int T[5] , Gr[NMax] , L[10];
bitset<NMax> a[NMax] ;
int b[NMax];
vector<int> ad[NMax];

void bkt()
{
	int mask,i,j,c;
	
	for (mask=1;mask<=(1<<L[0]);++mask)
	{
		c=1;
		for (i=0;i<L[0];++i) if ( (mask ^ (1<<i))<mask){
			++c;
			for (j=i-1;j>=0;--j) if ( (mask ^ (1<<j))<mask && !a[L[i+1]][L[j+1]])
				break;
			if (j>=0) break;
		}
		if (i==L[0])
			++T[c];
	}
}

void solve(int x)
{
	if ( b[x] ) return;
	b[x]=true;L[0]=0;
	for (typeof(ad[x].begin()) it = ad[x].begin() ; it<ad[x].end();++it) if ( !b[*it] )
		L[++L[0]]=*it;
	bkt();
	for (typeof(ad[x].begin()) it = ad[x].begin() ; it<ad[x].end();++it) if ( !b[*it] )
		--Gr[*it],a[x][*it]=false,a[*it][x]=false;
	for (typeof(ad[x].begin()) it = ad[x].begin() ; it<ad[x].end();++it) if ( !b[*it] && Gr[*it]<6)
		solve(*it);
}

int main()
{
	int i,x,y;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	for (i=0;i<M;++i)
		scanf("%d%d",&x,&y),
		a[x][y]=a[y][x]=true,
		ad[x].push_back(y),
		ad[y].push_back(x),
		++Gr[x],++Gr[y];
	fclose(stdin);
	
	for (i=1;i<=N;++i) if (Gr[i]<6)
		solve(i);
	
	freopen(OUT,"w",stdout);
	if (T[4]) printf("4 %d\n",T[4]);
	else if (T[3]) printf("3 %d\n",T[3]);
	else if (T[2]) printf("2 %d\n",T[2]);
	else printf("1 %d\n",T[1]);
	fclose(stdout);
	return 0;
}