#include <iostream>
#include <fstream>
#include <queue>
#include <set>

#define us unsigned short

using namespace std;

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

const int N = 30010;

int n, m, gr[N], trei, patru;
queue <us> q;
set <us> a[N];

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x, y;
        fin>>x>>y;
        a[x].insert(y);
        a[y].insert(x);
        gr[x]++, gr[y]++;
    }

    for(int i=1; i <= n; i++)
        if(gr[i] < 6)
        {
            q.push(i);
            break;
        }

    set <us> :: iterator ii, jj, k;
    while(!q.empty())
    {
        us x = q.front(); q.pop();
        for(ii = a[x].begin(); ii != a[x].end(); ii++)
        if(*ii > x)
        {
            for(jj = ii; jj != a[x].end(); jj++)
            if(*jj > *ii && a[*ii].count(*jj))
            {
                ++trei;
                for(k = jj; k != a[x].end(); k++)
                    if(*k > *jj && a[*ii].count(*k) && a[*jj].count(*k))
                        ++patru;
            }
        }
        for(ii = a[x].begin(); ii != a[x].end(); ii++)
        {
            a[*ii].erase(x);
            gr[*ii]--;
            if(gr[*ii] < 6) q.push(*ii);
        }
    }

    if(patru)
        fout<<4<<' '<<patru;
    else if(trei)
        fout<<3<<' '<<trei;
    else
        fout<<2<<' '<<m;
    return 0;
}