#include <fstream>
#include <map>
#include <set>

using namespace std;

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

const int nmax = 3e4 + 5;

int cate, cmax;

set< int > g[nmax + 1];
set< pair<int, int> > s;
map<pair<int, int>, bool> exista;

void k3 (int k) {
    for (auto i : g[ k ]) {
        for (auto j : g[ k ]) {
            if (i >= j) continue;
            if (exista.find(make_pair(i, j)) != exista.end()) {
                if (cmax < 3) {
                    cmax = 3; cate = 0;
                } if (cmax == 3) {
                    ++ cate;
                }
            }
        }
    }
}

void k4 (int k) {
    for (auto i : g[ k ]) {
        for (auto j : g[ k ]) {
            if (i >= j) continue;
            if (exista.find(make_pair(i, j)) != exista.end()) {
                for (auto shp : g[ k ]) {
                    if (j >= shp) continue;
                    if (exista.find(make_pair(shp, i)) == exista.end()) continue;
                    if (exista.find(make_pair(shp, j)) == exista.end()) continue;

                    if (cmax < 4) {
                        cmax = 4; cate = 0;
                    }
                    ++ cate;
                }
            }
        }
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; ++ i) {
        int x, y;
        fin >> x >> y;
        exista[ make_pair(x, y) ] = 1;
        exista[ make_pair(y, x) ] = 1;
        g[ x ].insert( y );
        g[ y ].insert( x );
    }

    cmax = 2; cate = m;

    for (int i = 1; i <= n; ++ i) {
        s.insert(make_pair((int)g[ i ].size(), i));
    }

    while (!s.empty()) {
        pair<int, int> k = *s.begin();
        s.erase( s.begin() );

        k3(k.second), k4(k.second);

        for (auto i : g[ k.second ]) {
            s.erase(make_pair(g[ i ].size(), i));
            g[ i ].erase(k.second);
            s.insert(make_pair(g[ i ].size(), i));
        }
    }

    fout << cmax << " " << cate << "\n";

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