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

#define MAX 30005
#define IS set<int>::iterator

using namespace std;

int N, M, A, B, sol[5];
set<int> S[MAX];
queue<int> Q;

int main()
{
    ifstream in("count.in"); in>>N>>M;
    for(int i = 1; i <= M; i++)
    {
        in>>A>>B;
        S[A].insert(B);
        S[B].insert(A);
    } in.close();
    sol[1] = N; sol[2] = M;
    for(int i = 1; i <= N; i++)
        if(S[i].size() < 6) Q.push(i);
    while(!Q.empty())
    {
        int nod = Q.front(); Q.pop();
        for(IS i = S[nod].begin(); i != S[nod].end(); i++)
            for(IS j = i; j != S[nod].end(); j++)
            {
                if(i == j || (S[*i].find(*j) == S[*i].end())) continue;
                sol[3]++;
                for(IS k = j; k != S[nod].end(); k++)
                {
                    if(j == k || S[*i].find(*k) == S[*i].end() || S[*j].find(*k) == S[*j].end()) continue;
                    sol[4]++;
                }
            }
        for(IS i = S[nod].begin(); i != S[nod].end(); i++)
        {
            S[*i].erase(nod);
            if(S[*i].size() < 6) Q.push(*i);
        }
        S[nod].clear();
    }
    ofstream out("count.out");
    for(int i = 4; i; i--)
    {
        if(sol[i])
        {
            out<<i<<" "<<sol[i];
            out.close();
            break;
        }
    }
    return 0;
}