#include <cstdio>
#include <set>

using namespace std;

#define maxn 30030

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

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);
        v[a].insert(b);
        v[b].insert(a);
    }

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

    while(!g.empty())
    {
        nod=*g.begin();
        g.erase(g.begin());

        for(set<int> :: iterator a=v[nod].begin(); a!=v[nod].end(); ++a)
        {
            ++s2;
            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.insert(*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;
}