#include <fstream>
#include <deque>
#include <set>

using namespace std;

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

int n,m,i,x,y,z,grad[30005],f[30005];
deque<int> c;
set<int> L[30005];

int main()
{
    fin >> n >> m; int c3 = 0; int c4 = 0;
    for (i=1; i<=m; i++)
    {
        fin >> x >> y;
        L[x].insert(y);
        L[y].insert(x);
        grad[x]++; grad[y]++;
    }
    for (i=1; i<=n; i++)
        if (grad[i] < 6)
        {
            c.push_back(i);
            f[i] = 1;
        }
    while (!c.empty())
    {
        int nod = c.front();
        for (set<int>::iterator it1=L[nod].begin(); it1!=L[nod].end(); it1++)
            for (set<int>::iterator it2=L[nod].begin(); it2!=L[nod].end(); it2++)
            {
                x = *it1; y = *it2;
                if (L[x].find(y) != L[x].end())
                    c3++;
            }
        for (set<int>::iterator it1=L[nod].begin(); it1!=L[nod].end(); it1++)
            for (set<int>::iterator it2=L[nod].begin(); it2!=L[nod].end(); it2++)
                for (set<int>::iterator it3=L[nod].begin(); it3!=L[nod].end(); it3++)
                {
                    x = *it1; y = *it2; z = *it3;
                    if (L[x].find(y) != L[x].end() && L[y].find(z) != L[y].end() && L[z].find(x) != L[z].end())
                        c4++;
                }
        c.pop_front();
        for (set<int>::iterator it1=L[nod].begin(); it1!=L[nod].end(); it1++)
        {
            grad[*it1]--;
            if (grad[*it1] < 6 && !f[*it1])
            {
                c.push_back(*it1);
                f[*it1] = 1;
            }
            L[*it1].erase(L[*it1].find(nod));
        }
    }
    if (c4) { fout << 4 << " " << c4/2; return 0; }
    if (c3) { fout << 3 << " " << c3/2; return 0; }
    fout << 2 << " " << m;
    return 0;
}