#include <fstream>
#include <algorithm>
#include <set>

using namespace std;

int N, M;
set<int> S[30002];
bool is[30002];
int maxdeg, degnow;

void Dfs(int x)
{
    is[x] = true;

    for (auto i = S[x].begin(); i != S[x].end(); ++i)
        for (auto j = S[x].begin(); j != S[x].end(); ++j)
            if (*j > *i && S[*i].find(*j) != S[*i].end())
            {
                if (maxdeg < 3)
                {
                    maxdeg = 3;
                    degnow = 1;
                }
                else if (maxdeg == 3)
                    ++degnow;

                for (auto k = S[x].begin(); k != S[x].end(); ++k)
                    if (*k > *i && *k > *j && S[*i].find(*k) != S[*i].end() && S[*j].find(*k) != S[*j].end())
                    {
                        if (maxdeg < 4)
                        {
                            maxdeg = 4;
                            degnow = 1;
                        }
                        else if (maxdeg == 4)
                            ++degnow;
                    }
            }

    for (auto i = S[x].begin(); i != S[x].end(); ++i)
        S[*i].erase(x);
    for (auto i = S[x].begin(); i != S[x].end(); ++i)
        if (S[*i].size() < 6 && !is[*i])
            Dfs(*i);
}

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

    fin >> N >> M;
    for (int i = 1, nod1, nod2; i <= M; ++i)
    {
        fin >> nod1 >> nod2;
        S[nod1].insert(nod2);
        S[nod2].insert(nod1);
    }

    maxdeg = 1;
    degnow = N;

    if (M >= N)
    {
        maxdeg = 2;
        degnow = M;
    }

    for (int i = 1; i <= N; ++i)
        if (S[i].size() < 6 && !is[i])
            Dfs(i);

    fout << maxdeg << ' ' << degnow << '\n';

    fin.close();
    fout.close();
}