#include <bits/stdc++.h>
#define DEF 30010

using namespace std;

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

int n, m, grad[DEF], viz[DEF], sol1, sol2, sol3, sol4;

set < int > L[DEF];

deque < int > Q;

vector < int > currNodes;

void check4nodes (int node1, int node2, int node3, int node4) {
    bool edge1to2 = (L[node1].find (node2) != L[node1].end ());
    bool edge1to3 = (L[node1].find (node3) != L[node1].end ());
    bool edge1to4 = (L[node1].find (node4) != L[node1].end ());
    bool edge2to3 = (L[node2].find (node3) != L[node2].end ());
    bool edge2to4 = (L[node2].find (node4) != L[node2].end ());
    bool edge3to4 = (L[node3].find (node4) != L[node3].end ());

    if (edge1to2 and edge1to3 and edge1to4 and edge2to3 and edge2to4 and edge3to4) {
        ++ sol4;
    }
}

void check3nodes (int node1, int node2, int node3) {
    bool edge1to2 = (L[node1].find (node2) != L[node1].end ());
    bool edge1to3 = (L[node1].find (node3) != L[node1].end ());
    bool edge2to3 = (L[node2].find (node3) != L[node2].end ());

    if (edge1to2 and edge1to3 and edge2to3) {
        ++ sol3;
    }
}

void calc (int node) {
    for (int i = 0; i < currNodes.size (); ++ i) {
        for (int j = i + 1; j < currNodes.size (); ++ j) {
            for (int k = j + 1; k < currNodes.size (); ++ k) {
                check4nodes (node, currNodes[i], currNodes[j], currNodes[k]);
            }
        }
    }

    for (int i = 0; i < currNodes.size (); ++ i) {
        for (int j = i + 1; j < currNodes.size (); ++ j) {
            check3nodes (node, currNodes[i], currNodes[j]);
        }
    }
}

int main () {

    fin >> n >> m;

    for (int i = 1; i <= m; ++ i) {
        int x, y;
        fin >> x >> y;
        L[x].insert (y);
        L[y].insert (x);
    }

    for (int i = 1; i <= n; ++ i) {
        if (L[i].size () <= 5) {
            Q.push_back (i);
            viz[i] = 1;
        }

        grad[i] = L[i].size ();

    }

    while (!Q.empty ()) {
        int currNode = Q.front ();
        Q.pop_front ();

        for (auto it : L[currNode]) {
            currNodes.push_back (it);
        }

        calc (currNode);
        currNodes.clear ();

        for (auto it : L[currNode]) {
            -- grad[it];
            L[it].erase (currNode);

            if (grad[it] <= 5 and viz[it] == 0) {
                Q.push_back (it);
                viz[it] = 1;
            }
        }
        L[currNode].clear ();
    }

    sol1 = n;
    sol2 = m;

    if (sol4 == 0) {
        if (sol3 == 0) {
            if (sol2 == 0) {
                fout << "1 " << sol1;
            }
            else {
                fout << "2 " << sol2;
            }
        }
        else {
            fout << "3 " << sol3;
        }
    }
    else {
        fout << "4 " << sol4;
    }

    return 0;
}