#include <fstream>
#include <set>

using namespace std;

const char InFile[]="count.in";
const char OutFile[]="count.out";
const int MaxN=30111;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,M,x,y,s3,s4,C[MaxN];
set<int> G[MaxN];

int main()
{
	fin>>N>>M;
	for(register int i=1;i<=M;++i)
	{
		fin>>x>>y;
		G[x].insert(y);
		G[y].insert(x);
	}
	fin.close();

	for(register int i=1;i<=N;++i)
	{
		if(G[i].size()<=5)
		{
			C[++C[0]]=i;
		}
	}

	int ind=1;
	while(ind<=C[0])
	{
		for(set<int>::iterator it1=G[C[ind]].begin();it1!=G[C[ind]].end();++it1)
		{
			for(set<int>::iterator it2=it1;it2!=G[C[ind]].end();++it2)
			{
				if(*it2>*it1 && G[*it2].find(*it1)!=G[*it2].end())
				{
					++s3;
					for(set<int>::iterator it3=it2;it3!=G[C[ind]].end();++it3)
					{
						if(*it3>*it2 && G[*it3].find(*it1)!=G[*it3].end() && G[*it3].find(*it2)!=G[*it3].end())
						{
							++s4;
						}
					}
				}
			}
		}

		for(set<int>::iterator it=G[C[ind]].begin();it!=G[C[ind]].end();++it)
		{
			G[*it].erase(C[ind]);
			if(G[*it].size()==5)
			{
				C[++C[0]]=*it;
			}
		}

		++ind;
	}

	if(s4)
	{
		fout<<"4 "<<s4;
	}
	else if(s3)
	{
		fout<<"3 "<<s3;
	}
	else
	{
		fout<<"2 "<<M;
	}
	fout.close();
	return 0;
}