#include <fstream>
#include <cstdlib>
#include <queue>
#define NM 30005
#define inf 1000000000

using namespace std;

ifstream fin("count.in");
ofstream fout("count.out");

int n, m, *A[NM], Grad[NM], Cd[NM];
bool Valid[NM], inq[NM];
int st, fi, maxim;
long long sol1, sol2, sol3;

struct muchie {int x, y;};

muchie Much[200];
int last;

bool Add(int x, int y)
{
    int i;
    if (A[x][0]>A[y][0])
        swap(x, y);
    for (i=1; i<=A[x][0]; i++)
    {
        if (A[x][i]==y)
        {
            Much[++last].x=x;
            Much[last].y=y;
            return 1;
        }
    }
    return 0;
}

bool Val(int x, int y)
{
    int i;
    for (i=1; i<=last; i++)
    {
        if ((Much[i].x==x && Much[i].y==y)||(Much[i].x==y && Much[i].y==x))
            return 1;
    }
    return 0;
}

void Test(int x)
{
    int i, j, k, n1, n2;
    for (i=1; i<=A[x][0]; i++)
    {
        n1=A[x][i];
        for (j=i+1; j<=A[x][0]; j++)
        {
            n2=A[x][j];
            if (Valid[n1]==0 && Valid[n2]==0)
                if(Add(n1, n2))
                    sol2++;
        }
    }
    for (i=1; i<=A[x][0]; i++)
        for (j=i+1; j<=A[x][0]; j++)
            for (k=j+1; k<=A[x][0]; k++)
            {
                if (Val(A[x][i], A[x][j]) && Val(A[x][i], A[x][k]) && Val(A[x][k], A[x][j]))
                {
                    sol3++;
                }
            }
    sol1+=A[x][0];
}

void Initz()
{
    int i;
    for (i=1; i<=n; i++)
    {
        if (Grad[i]<6)
        {
            fi++;
            Cd[fi]=i;
            inq[i]=1;
        }
    }
}

void Decrese()
{
    int i, p, j;
    p=Cd[st];
    for (i=1; i<=A[p][0]; i++)
    {
        Grad[A[p][i]]--;
        if (Grad[A[p][i]]<6 && inq[A[p][i]]==0)
        {
            Cd[++fi]=A[p][i];
            inq[A[p][i]]=1;
        }
    }
}

int main()
{
    int i, x ,y, j;
    fin>>n>>m;
    for (i=1; i<=n; i++)
    {
        A[i] = (int *) realloc (A[i], sizeof(int));
        A[i][0]=0;
    }
    for (i=1; i<=m; i++)
    {
        fin>>x>>y;
        Grad[x]++;
        Grad[y]++;
        A[x][0]++;
        A[x] = (int *) realloc (A[x], (A[x][0]+1)*sizeof(int));
        A[x][A[x][0]]=y;
        A[y][0]++;
        A[y] = (int *) realloc (A[y], (A[y][0]+1)*sizeof(int));
        A[y][A[y][0]]=x;
    }
    int p;
    Initz();
    st=1;
    for (i=1; i<=n; i++)
    {
        p=Cd[st];
        last=0;
        Test(p);
        Valid[p]=1;
        Decrese();
        st++;
    }
    if (sol3>0)
        fout<<4<<" "<<sol3;
    else
        if (sol2>0)
            fout<<3<<" "<<sol2;
        else
            fout<<2<<" "<<sol1;

    return 0;
}