#include<fstream>
#include<algorithm>
#define x first
#define y second
using namespace std;
ifstream fin("count.in");
ofstream fout("count.out");
const int DN=3e4+5;
int n,m,nr;
long long cf[DN],bit,t,cnt[2];
long long b[DN];
pair<int,int>a[2*DN];
int z[(1<<20)+5];
void solve(long long t)
{
    if(t==0)
        return;
    long long nr=0;
	for(int i=0;i<3;i++)
	{
		cnt[0]+=z[t%(1<<20)];
		nr+=z[t%(1<<20)];
		t>>=20;
	}
	nr*=nr-1;
	nr/=2;
	if(nr)
        cnt[1]+=nr;
}
int main()
{
	for(int i=0;i<(1<<10);i++)
		for(int j=0;j<10;j++)
			if(i&(1<<j))
				z[i]++;
	for(int i=(1<<10);i<(1<<20);i++)
		z[i]=z[i%1024]+z[(i>>10)];
	fin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		fin>>a[i].x>>a[i].y;
		if(a[i].x<a[i].y)
			swap(a[i].x,a[i].y);
	}
	sort(a+1,a+m+1);
	for(int h=n;h>0;h--)
	{
		bit=h-1;
		bit%=60;
		if(bit==59)
			for(int i=1;i<=n;i++)
			{
				cf[i]=0;
				b[i]=0;
			}
		bit=(1LL<<bit);
		b[h]=bit;
		if(bit==1)
			for(int i=m;i>0;i--)
			{
			    if(a[i].x==a[i].y)
                    continue;
				t=(cf[a[i].x]&cf[a[i].y]);
				solve(t);
				cf[a[i].y]|=b[a[i].x];
			}
	}
	nr=3;
	if(cnt[0]==0)
	{
		fout<<2<<' '<<m;
		return 0;
	}
	if(cnt[1])
    {
        fout<<4<<' '<<cnt[1];
        return 0;
    }
	fout<<nr<<' '<<cnt[0];
}