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

using namespace std;

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

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

struct muchie
{
    int x, y;
};

set < int > A[NM];
set < int >::iterator it1;
set < int >::iterator it2;
set < int >::iterator it3;

muchie Much[200];
int last;



void Test(int x)
{
    for (it1=A[x].begin(); it1!=A[x].end(); it1++)
    {
        if (Valid[*it1]==0)
            for (it2=it1; it2!=A[x].end(); it2++)
            {
                if (A[*it1].find(*it2)!=A[*it1].end() && Valid[*it2]==0)
                {
                    sol2++;
                    for (it3=it2; it3!=A[x].end(); it3++)
                    {
                        if (Valid[*it3]==0 && A[*it2].find(*it3)!=A[*it2].end() && A[*it3].find(*it1)!=A[*it3].end())
                        {
                            sol3++;
                        }
                    }
                }
            }
    }

}

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<=L[p]; i++)
    {
        Grad[L[p]]--;
        if (Grad[L[p]]<6 && inq[L[p]]==0)
        {
            Cd[++fi]=L[p];
            inq[L[p]]=1;
        }
    }
}

int main()
{
    int i, x,y, j;
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        fin>>x>>y;
        Grad[x]++;
        Grad[y]++;
        L[x]++;
        A[x].insert(y);
        L[y]++;
        A[y].insert(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<<" "<<m;
    return 0;
}