#include <fstream>
#include <vector>
#include <set>
#define NM 30010

using namespace std;

ifstream f("count.in");
ofstream g("count.out");

int N, M;
bool In[NM];
set<int> G[NM];
int DG[NM], Count[10];
vector<int> V;


set< pair<int, int> > Nodes;
set< pair<int, int> >::iterator it;

bool Check (int a, int b, int c)
{
    if (G[a].find(b)==G[a].end() || G[a].find(c)==G[a].end() || G[b].find(c)==G[b].end()) return 0;
    return 1;
}

bool Check (int a, int b, int c, int d)
{
    if (G[a].find(b)==G[a].end() || G[a].find(c)==G[a].end() || G[a].find(d)==G[a].end()) return 0;
    if (G[b].find(c)==G[b].end() || G[b].find(d)==G[b].end() || G[c].find(d)==G[c].end()) return 0;
    return 1;
}

void Solve ()
{
    if (V.size()<=2) return;

    int i, j, k;
    for (i=1; i<V.size(); i++)
        for (j=i+1; j<V.size(); j++)
        {
            if (Check(V[0], V[i], V[j]))
                Count[3]++;
            for (k=j+1; k<V.size(); k++)
                if (Check(V[0], V[i], V[j], V[k]))
                    Count[4]++;
        }
}

int main ()
{
    f >> N >> M;
    for (int i=1; i<=M; i++)
    {
        int a, b;
        f >> a >> b;
        G[a].insert(b);
        G[b].insert(a);

        DG[a]++;
        DG[b]++;
    }
    Count[1]=N;
    Count[2]=M;

    for (int i=1; i<=N; i++)
    {
        In[i]=1;
        Nodes.insert(make_pair(DG[i], i));
    }

    while (!Nodes.empty())
    {
        it=Nodes.begin();
        int node=it->second;
        Nodes.erase(it);

        V.clear();
        V.push_back(node);
        In[node]=0;

        for (set<int>::iterator v=G[node].begin(); v!=G[node].end(); ++v)
            if (In[*v])
                V.push_back(*v);

        Solve();
        for (vector<int>::iterator x=V.begin(); x!=V.end(); ++x)
            if (*x!=node && DG[*x]>2)
            {
                Nodes.erase(make_pair(DG[*x], *x));
                DG[*x]--;
                Nodes.insert(make_pair(DG[*x], *x));
            }
    }

    for (int i=4; i>=1; i--)
        if (Count[i]!=0)
        {
            g << i << ' ' << Count[i] << '\n';
            break;
        }

    f.close();
    g.close();

    return 0;
}