#include<stdio.h>
#include<vector>

#define maxn 30005

using namespace std;

FILE*f=fopen("count.in","r");
FILE*g=fopen("count.out","w");

int n,m,i,x,y,s3,s4,nod,p,u;
int Gr[maxn],viz[maxn],X[10],Q[maxn],inq[maxn];
vector<int>G[maxn],W[maxn];

inline bool connected ( int niv , int nodvcn ){
	int ok = 1;
	for ( int i = 1 ; i <= niv ; ++i ){
		int ok2 = 0;
		for ( vector<int>::iterator itt = G[X[i]].begin() ; itt != G[X[i]].end() ; ++itt ){
			if ( (*itt) == nodvcn ){
				ok2 = 1; break ;
			}
		}
		if ( !ok2 ){
			ok = 0; break ;
		}
	}
	return ok;
}

void back ( int nod , int niv ){
	
	viz[nod] = 1; X[niv] = nod;
	if ( niv == 3 ) ++s3;
	if ( niv == 4 ){
		++s4,viz[nod] = 0;
		return;
	}
	for ( vector<int>::iterator itt = W[nod].begin() ; itt != W[nod].end() ; ++itt ){
		int nodvcn = (*itt);
		if ( !viz[nodvcn] && connected(niv,nodvcn) && nodvcn > nod ){
			back(nodvcn,niv+1);
		}
	}
	viz[nod] = 0; X[niv] = 0;
}

int main () {
	
	fscanf(f,"%d %d",&n,&m);
	for ( i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d",&x,&y); ++Gr[x]; ++Gr[y];
		G[x].push_back(y);
		G[y].push_back(x);
		if ( x < y )	W[x].push_back(y);
		else	W[y].push_back(x);
	}
	
	for ( i = 1 ; i <= n ; ++i ){
		if ( Gr[i] <= 5 )
			Q[++u] = i,inq[i] = 1;
	}
	
	for ( p = 1 ; p <= u ; ++p ){
		nod = Q[p];
		back(nod,1);
		for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
			if ( !viz[*itt] && !inq[*itt] ){
				--Gr[*itt]; if ( Gr[(*itt)] <= 5 )	Q[++u] = (*itt),inq[*itt] = 1;
			}
		}
	}
	
	if ( s4 ){
		fprintf(g,"4 %d\n",s4);
	}
	else{
		if ( s3 ){
			fprintf(g,"3 %d\n",s3);
		}
		else{
			fprintf(g,"2 %d\n",m);
		}
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}