#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;

struct SetComp
{
    bool operator () (const int& a, const int& b) const
    {
        return DG[a]<DG[b];
    }
};
set<int, SetComp> Nodes;
set<int, SetComp>::iterator it;

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

    int a, b, c, d;

    if (V.size()==3)
    {
        a=V[0];
        b=V[1];
        c=V[2];

        if (G[a].find(b)==G[a].end() || G[a].find(c)==G[a].end() || G[b].find(c)==G[b].end()) return;
        Count[3]++;
    }
    else
    {
        a=V[0];
        b=V[1];
        c=V[2];
        d=V[3];

        if (G[a].find(b)!=G[a].end() && G[a].find(c)!=G[a].end() && G[b].find(c)!=G[b].end()) Count[3]++;
        if (G[a].find(b)!=G[a].end() && G[a].find(d)!=G[a].end() && G[b].find(d)!=G[b].end()) Count[3]++;
        if (G[a].find(c)!=G[a].end() && G[a].find(d)!=G[a].end() && G[c].find(d)!=G[c].end()) Count[3]++;

        if (G[a].find(b)!=G[a].end() && G[a].find(c)!=G[a].end() && G[a].find(d)!=G[a].end() && G[b].find(c)!=G[b].end() && G[b].find(d)!=G[b].end() && G[c].find(d)!=G[c].end()) 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(i);
    }

    while (!Nodes.empty())
    {
        it=Nodes.begin();
        int node=*it;
        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)
            {
                Nodes.erase(*x);
                DG[*x]--;
                Nodes.insert(*x);
            }
    }

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

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

    return 0;
}