#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

const int N = (1<<15);

vector<int> a[N];
vector<pair<int,int> > d;
map<int,int> h[N];
int n,m,maxx,nrx,gr[N];

void citire()
{
	int i,x,y,nr=0;
	scanf("%d%d",&n,&m);
	d.resize(n);
	for(i=0;i<n;++i)
	{
		d[i].first=0;
		d[i].second=1+i;
	}
	maxx=2;
	nrx=m;
	while(m--)
	{
		scanf("%d%d",&x,&y);
		++d[x-1].first;
		++d[y-1].first;
		++gr[x];
		++gr[y];
		a[x].push_back(y);
		a[y].push_back(x);
		h[x][y]=++nr;
		h[y][x]=++nr;
	}
	sort(d.begin(),d.end());
}

inline bool ok3(int x,int y,int z)
{
	return h[x].find(y)!=h[x].end() && h[x].find(z)!=h[x].end() && h[y].find(z)!=h[y].end();
}

inline bool ok2(int x,int y)
{
	return h[x].find(y)!=h[x].end();
}

void complet(int x)
{
	int i,j,k,nr=a[x].size();
	for(i=0;i<nr;++i)
		for(j=i+1;j<nr;++j)
			for(k=j+1;k<nr;++k)
				if(ok3(a[x][i],a[x][j],a[x][k]))
				{
					if(maxx==4)
						++nrx;
					if(maxx!=4)
					{
						maxx=4;
						nrx=1;
					}
				}
	if(maxx!=4)
	{
		for(i=0;i<nr;++i)
			for(j=i+1;j<nr;++j)
				if(ok2(a[x][i],a[x][j]))
				{
					if(maxx==3)
						++nrx;
					if(maxx<3)
					{
						maxx=3;
						nrx=1;
					}
				}
	}
	for(i=0;i<nr;++i)
	{
		k=a[x][i];
		if(h[x].find(k)!=h[x].end())
		{
			h[x].erase(k);
			--gr[x];
		}
		if(h[k].find(x)!=h[k].end())
		{
			h[k].erase(x);
			--gr[k];
		}
	}
	for(i=0;i<nr;++i)
	{
		k=a[x][i];
		if(gr[k] && gr[k]<6)
			complet(k);
	}
}

void calcul()
{
	int i;
	for(i=0;i<n;++i)
		if(gr[d[i].second])
			complet(d[i].second);
	printf("%d %d\n",maxx,nrx);
}

int main()
{
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	citire();
	calcul();
	return 0;
}