#include <bits/stdc++.h>

using namespace std;

set < int > g[20009];
set < int > :: iterator it;
set < pair < int , int > > aset;
set < pair < int , int > > :: iterator itP;
int deg[20009];
vector < int > tmp;
int ways[5] , n , m , _a , _b , _c , a , b , c , i , x;

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

scanf("%d" , &n);
scanf("%d" , &m);

for (i = 1 ; i <= m ; ++i)
{
    scanf("%d" , &a);
    scanf("%d" , &b);

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

    deg[a] += 1 , deg[b] += 1;
}

for (i = 1 ; i <= n ; ++i)
aset.insert(make_pair(deg[i] , i));

for (i = 1 ; i <= n ; ++i)
{
    x = (*aset.begin()).second;

    tmp.clear();
    for (it = g[x].begin() ; it != g[x].end() ; ++it)
    tmp.push_back(*it);

    // fac clica de 1
    ways[1] += 1;

    // fac clica de 2
    ways[2] += deg[x];

    // fac clica de 3
    for (_a = 0 ; _a < tmp.size() ; ++_a)
    {
        a = tmp[_a];
        for (_b = 0 ; _b < _a ; ++_b)
        {
            b = tmp[_b];

            it = g[a].find(b);
            if (it == g[a].end()) continue;

            ways[3] += 1;
        }
    }

    //fac clica de 4
    for (_a = 0 ; _a < tmp.size() ; ++_a)
    {
        a = tmp[_a];
        for (_b = 0 ; _b < _a ; ++_b)
        {
            b = tmp[_b];
            it = g[a].find(b);
            if (it == g[a].end()) continue;

            for (_c = 0 ; _c < _b ; ++_c)
            {
                c = tmp[_c];

                it = g[a].find(c);
                if (it == g[a].end()) continue;

                it = g[b].find(c);
                if (it == g[b].end()) continue;

                ways[4] += 1;
            }
        }
    }

    //elimin nodul
    aset.erase(aset.begin());
    for (_a = 0 ; _a < tmp.size() ; ++_a)
    {
        a = tmp[_a];
        it = g[a].find(x);
        g[a].erase(it);

        itP = aset.find(make_pair(deg[a] , a));
        aset.erase(itP);

        deg[a]--;
        aset.insert(make_pair(deg[a] , a));
    }
}

for (i = 4 ; i ; --i)
if (ways[i]) break;

printf("%d %d\n" , i , ways[i]);

return 0;
}