#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;
long long b[DN];
pair<int,int>a[2*DN];
int z[(1<<20)+5];
void solve(long long t)
{
    if(t==0)
        return;
	for(int i=0;i<3;i++)
	{
		cnt+=z[t%(1<<20)];
		t>>=20;
	}
}
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)
	{
		nr=2;
		cnt=m;
	}
	fout<<nr<<' '<<cnt;
}