#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\n%d\n",n4); else
		if (n3) printf("3\n%d\n",n3); else
			printf("%d\n",m);
	return 0;
}