#include <cstdio>
#include <set>

using namespace std;

#define maxn 30030

int n, m, i, j, k, s2, s3, s4, g0, nod;
set<int> v[maxn];
int g[maxn];

int main()
{
    freopen("count.in", "r", stdin);
    freopen("count.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; ++i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        ++s2;
        v[a].insert(b);
        v[b].insert(a);
    }

    for(int i=1; i<=n; ++i)
        if(v[i].size()<=5)
            g[++g0]=i;

    for(int i=1; i<=g0; ++i)
    {
        nod=g[i];

        if(v[nod].size()>=2)
            for(set<int> :: iterator a=v[nod].begin(); a!=v[nod].end(); ++a)
                for(set<int> :: iterator b=v[*a].begin(); b!=v[*a].end(); ++b)
                {
                    if(*b<=*a || *b==nod || v[*b].find(nod)==v[*b].end())
                        continue;
                    ++s3;
                    for(set<int> :: iterator c=v[*b].begin(); c!=v[*b].end(); ++c)
                    {
                        if(*c<=*b || *c==nod || v[*c].find(nod)==v[*c].end() || v[*c].find(*a)==v[*c].end())
                            continue;
                        ++s4;
                    }
                }

        for(set<int> :: iterator it=v[nod].begin(); it!=v[nod].end(); ++it)
        {
            v[*it].erase(nod);
            if(v[*it].size()==5)
                g[++g0]=*it;
        }
    }

    if(s4>0)
    {
        printf("4 %d\n", s4);
        return 0;
    }
    if(s3>0)
    {
        printf("3 %d\n", s3);
        return 0;
    }
    printf("2 %d\n", m);
    return 0;
}