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

using namespace std;

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

int N, M;
int sol, nrsol;
set<int> S[30005];
queue<int> Q;
bool used[30005];

void solve()
{
    while (!Q.empty())
    {
        int nod = Q.front();
        Q.pop();

        for (set<int>::iterator it = S[nod].begin(); it != S[nod].end(); ++it)
            for (set<int>::iterator it1 = S[nod].begin(); it1 != S[nod].end(); ++it1)
            {
                if (*it1 > *it && S[*it].find(*it1) != S[*it].end())
                {
                    if (sol < 3)
                    {
                        sol = 3;
                        nrsol = 1;
                    }
                    else if (sol == 3)
                        ++nrsol;

                    for (set<int>::iterator it2 = S[nod].begin(); it2 != S[nod].end(); ++it2)
                    {
                        if (*it2 > *it1 && S[*it1].find(*it2) != S[*it1].end() && S[*it].find(*it2) != S[*it].end())
                        {
                            if (sol < 4)
                            {
                                sol = 4;
                                nrsol = 4;
                            }
                            else if (sol == 4)
                                ++nrsol;
                        }
                    }
                }
            }

        for (set<int>::iterator it = S[nod].begin(); it != S[nod].end(); ++it)
            S[*it].erase(nod);
        for (set<int>::iterator it = S[nod].begin(); it != S[nod].end(); ++it)
            if (S[*it].size() <= 5 && !used[*it])
            {
                used[*it] = true;
                Q.push(*it);
            }
    }
}

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

    sol = 1;
    nrsol = N;

    if (M > 0)
    {
        sol = 2;
        nrsol = M;
    }

    for (int i = 1; i <= N; ++i)
        if (S[i].size() <= 5)
        {
            used[i] = true;
            Q.push(i);
        }

    solve();

    fout << sol << ' ' << nrsol << '\n';

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