#include <stdio.h>
#include <vector>
#include <queue>
#define Nmax 30002
#define Prim 666013
#define pb push_back

using namespace std;

queue< int > Q;
vector< int > v[Nmax];
vector< int > Hash[Prim];
int gr[Nmax],use[Nmax],inq[Nmax],vec[6],wh[6];
int N,M;

inline void insert_hash(int val){
	Hash[val%Prim].pb(val);
}
inline int find_hash(int x,int y){
	vector< int >:: iterator it;
	int val=(x<<16)+y,unde=val%Prim;
	for(it=Hash[unde].begin(); it!=Hash[unde].end(); ++it)
		if( *it==val ) return 1;
	return 0;
}	

int main(){
	vector< int >:: iterator it;
	int f,i,j,x,y,k,ok,max1,max2;
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(i=1;i<=M;++i){
		scanf("%d%d",&x,&y);
		v[x].pb(y); gr[x]++;
		v[y].pb(x); gr[y]++;
		insert_hash((x<<16)+y);
		insert_hash((y<<16)+x);
	}
	
	for(i=1;i<=N;++i)
		if( gr[i] < 6 ){
			Q.push(i);
			inq[i]=1;
		}

	max1=0; max2=N;
	while( ! Q.empty() ){
		f=Q.front(); Q.pop();
		use[f]=1;
		
		vec[0]=0;
		for(it=v[f].begin(); it!=v[f].end(); ++it)
		if( !use[*it] ){
			vec[++vec[0]]=*it;
			gr[*it]--;
			if( gr[*it]<6 && !inq[*it]){
				inq[*it]=1;
				Q.push(*it);
			}
		}
		
		for(i=1;i<(1<<vec[0]);++i){
			wh[0]=0;
			for(j=0;j<vec[0];++j)
				if( i & (1<<j) )
					wh[++wh[0]]=vec[j+1];
			ok=wh[0] >= max1;
			for(j=1;j<wh[0] && ok;++j)
				for(k=j+1;k<=wh[0] && ok;++k)
					if( ! find_hash(wh[j],wh[k]) ){
						ok=0; break;
					}
			if( ok ) 
				if( wh[0] > max1 ) max1=wh[0], max2=1;
				else max2++;
		}
	}
	
	printf("%d %d\n",max1+1,max2);
	fclose(stdin); fclose(stdout);
	return 0;
}