#include <cstdio>
#include <set>
#include <queue>

using namespace std;

typedef set<int>::iterator sii;

const int MaxN = 30005;

set<int> G[MaxN];
int N, Degree[MaxN], Sol[5];
queue<int> Q;

inline void InitQ() {
    for (int X = 1; X <= N; ++X)
        if (Degree[X] < 6)
            Q.push(X);
}

void Count(int X) {
    for (sii x = G[X].begin(); x != G[X].end(); ++x) {
        for (sii y = x; y != G[X].end(); ++y) {
            if (G[*x].find(*y) == G[*x].end())
                continue;
            ++Sol[3];
            for (sii z = y; z != G[X].end(); ++z)
                Sol[4] += (G[*z].find(*x) != G[*z].end() && G[*z].find(*y) != G[*z].end());
        }
    }
}

inline void Erase(int X) {
    for (set<int>::iterator Y = G[X].begin(); Y != G[X].end(); ++Y)
        G[*Y].erase(X);
    G[X].clear();
}

void Solve() {
    for (InitQ(); !Q.empty(); Q.pop()) {
        int X = Q.front();
        Count(X);
        Erase(X);
    }
}

void Read() {
    freopen("count.in", "r", stdin);
    int M; scanf("%d %d", &N, &M);
    Sol[1] = N, Sol[2] = M;
    for (; M; --M) {
        int X, Y; scanf("%d %d", &X, &Y);
        G[X].insert(Y), G[Y].insert(X);
        ++Degree[X], ++Degree[Y];
    }
}

void Print() {
    freopen("count.out", "w", stdout);
    int Size;
    for (Size = 4; Size > 0 && !Sol[Size]; --Size);
    printf("%d %d\n", Size, Sol[Size]);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}