#include<iostream>
#include<fstream>
#include<queue>
#include<set>
using namespace std;

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

int n,m,sol1,sol2;
set<int> g[30010];
queue<int> q;

int main()
{
    int i,a,b,el;
    set<int>::iterator it,j,k;

    in >> n >> m;

    for(i=1; i<=m; ++i)
    {
        in >> a >> b;

        g[a].insert(b);
        g[b].insert(a);
    }

    for(i=1; i<=n; ++i) {
        if(g[i].size()<6) {
            q.push(i);
        }
    }

    while(!q.empty())
    {
        el = q.front();
        q.pop();

        for(it = g[el].begin(); it!=g[el].end(); ++it)
            for(j = it; j!=g[el].end(); ++j)
                if(*j > *it && g[*it].count(*j) > 0)
                {

                    sol1++;
                    for(k=j; k!=g[el].end(); ++k)
                        if(*k>*j && g[*it].count(*k) > 0 && g[*j].count(*k) > 0)
                            ++sol2;
                }

        for(it = g[el].begin(); it!=g[el].end(); ++it)
        {
            g[*it].erase(el);

            if(g[*it].size() == 5)
                q.push(*it);
        }
    }

    if(sol2)
        out << "4 " << sol2 << "\n";
    else if(sol1)
        out << "3 " <<  sol1 << "\n";
    else
        out << "2 " << m << "\n";

    in.close();
    out.close();

    return 0;
}