#include<cstdio>
#include<set>
using namespace std;
set<int>v[30002];
int l[30002],c0;
int main(){
	int n,m,i,j,n3=0,n4=0;
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=m;++i){
		int a,b;
		scanf("%d %d",&a,&b);
		v[a].insert(b);v[b].insert(a);
	}
	for (i=1;i<=n;++i)
		if (v[i].size()<6)
			l[++c0]=i;
	for (j=1;j<=c0;++j){
		i=l[j];
		set<int>::iterator a,b,c;
		for (a=v[i].begin();a!=v[i].end();++a){
			v[*a].erase(v[*a].find(i));
			if (v[*a].size()==5) l[++c0]=*a;
			for (b=a,++b;b!=v[i].end();++b)
				if (v[*a].find(*b)!=v[*a].end()){
					++n3;
					for (c=b,++c;c!=v[i].end();++c)
						if ((v[*a].find(*c)!=v[*a].end()) && (v[*b].find(*c)!=v[*b].end()))
							++n4;
				}
		}
	}
	if (n4) printf("4 %d\n",n4); else
		if (n3) printf("3 %d\n",n3); else
			printf("2 %d\n",m);
	return 0;
}