using namespace std;
#include<cstdio>
#include<string>
#include<set>
#define Nm 30001
set<int> G[Nm];
int D[Nm],n,a,b;

void read()
{
    int m,x,y;

    freopen("count.in","r",stdin);
    scanf("%d%d",&n,&m);
    a=2; b=m;
    while(m--)
    {
        scanf("%d%d",&x,&y);
        G[x].insert(y);
        G[y].insert(x);
        ++D[x]; ++D[y];
    }
}

void solve()
{
    set<int>::iterator it1,it2,it3;
    int Q[Nm],Viz[Nm],l=0,r=-1,i,x;

    memset(Viz,0,sizeof(Viz));
    for(i=1;i<=n;++i)
        if(D[i]<6)
        {
            Q[++r]=i;
            Viz[i]=1;
        }

    while(l<=r)
    {
        x=Q[l++];
        if(D[x]>2)
            for(it1=G[x].begin();it1!=G[x].end();++it1)
                for(++it1,it2=it1,--it1;it2!=G[x].end();++it2)
                    for(++it2,it3=it2,--it2;it3!=G[x].end();++it3)
                        if(G[*it1].find(*it2)!=G[*it1].end() && G[*it1].find(*it3)!=G[*it1].end() && G[*it2].find(*it3)!=G[*it2].end())
                            if(a<4)
                            {
                                a=4;
                                b=1;
                            }
                            else
                                ++b;

        if(D[x]>1 && a<4)
            for(it1=G[x].begin();it1!=G[x].end();++it1)
                for(++it1,it2=it1,--it1;it2!=G[x].end();++it2)
                    if(G[*it1].find(*it2)!=G[*it1].end())
                        if(a<3)
                        {
                            a=3;
                            b=1;
                        }
                        else
                            ++b;
        for(it1=G[x].begin();it1!=G[x].end();++it1)
        {
            G[*it1].erase(G[*it1].find(x));
            --D[*it1];
            if(D[*it1]<6 && !Viz[*it1])
            {
                Q[++r]=*it1;
                Viz[*it1]=1;
            }
        }
    }
}

void write()
{
    freopen("count.out","w",stdout);
    printf("%d %d\n",a,b);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}