#include<fstream>
#include<set>
#include<queue>
using namespace std;
int n,m,sol3,sol4;
set <int> G[30010];
queue <int> Q;
int grad[30010];

int main()
{
	int i,x,y;
	set <int>::iterator it,jt,kt;
	ifstream fin("count.in");
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		G[x].insert(y);
		G[y].insert(x);
		grad[x]++;
		grad[y]++;
	}
	fin.close();
	
	for(i=1;i<=n;i++)
		if(grad[i]<6)
			Q.push(i);
	while(!Q.empty())
	{
		x=Q.front();
		Q.pop();
		for(it=G[x].begin();it!=G[x].end();it++)
		{
			for(jt=it;jt!=G[x].end();jt++)
			{
				if(*jt!=*it && G[*it].count(*jt)>0)
				{
					sol3++;
					for(kt=jt;kt!=G[x].end();kt++)
					{
						if(*kt!=*jt && G[*it].count(*kt)>0 && G[*jt].count(*kt)>0)
							sol4++;
					}
				}
			}
		}
		for(it=G[x].begin();it!=G[x].end();it++)
		{
			G[*it].erase(x);
			grad[*it]--;
			if(grad[*it]==5)
				Q.push(*it);
		}
	}
	
	ofstream fout("count.out");
	if(sol4>0)
		fout<<"4 "<<sol4<<"\n";
	else
	{
		if(sol3>0)
			fout<<"3 "<<sol3<<"\n";
		else
			fout<<"2 "<<m<<"\n";
	}
	fout.close();
	return 0;
}