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

#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];

struct mch{
	int x;
	int y;
	
	mch(int x = 0,int y = 0):x(x),y(y){}
	
	friend bool operator < ( const mch &a , const mch &b ){
		if ( a.x != b.x )
			return a.x < b.x;
		return a.y < b.y;
	}
};

set<mch>Set;

inline bool connected ( int niv , int nodvcn ){
	int ok = 1;
	for ( int i = 1 ; i <= niv ; ++i ){
		if ( Set.find(mch(X[i],nodvcn)) == Set.end() ){
			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 = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
		int nodvcn = (*itt);
		if ( !viz[nodvcn] && connected(niv,nodvcn) ){
			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);
		Set.insert(mch(x,y)); Set.insert(mch(y,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); viz[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] = nod,inq[nod] = 1;
			}
		}
	}
	
	if ( s4 ){
		fprintf(g,"4 %d\n",s4/6);
	}
	else{
		if ( s3 ){
			fprintf(g,"3 %d\n",s3/2);
		}
		else{
			fprintf(g,"2 %d\n",m);
		}
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}