//prea mult stl dauneaza
#include <bits/stdc++.h>

using namespace std;

const int nmax = 3e4 + 10;

int ans[5];

int n, m;
int q[nmax]; bool in_q[nmax];

set < int > g[nmax];


void input() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);

        g[x].insert(y);
        g[y].insert(x);
    }
}

void solve() {
    for (int i = 1; i <= n; ++i) {
        if (g[i].size() <= 5) q[++q[0]] = i, in_q[i] = 1;
    }

    for (int i = 1; i <= q[0]; ++i) {
        int x = q[i];

        for (auto y = g[x].begin(); y != g[x].end(); ++y) {
            ans[2]++; auto z = y; z++;
            for ( ; z != g[x].end(); ++z) {
                if (g[*y].find(*z) == g[*y].end()) continue;
                ans[3]++; auto w = z; w++;
                for ( ; w != g[x].end(); ++w) {
                    if (g[*w].find(*y) == g[*w].end() || g[*w].find(*z) == g[*w].end()) continue;
                    ans[4]++;
                }
            }
        }

        for (auto y : g[x]) {
            g[y].erase(x);
            if (g[y].size() <= 5 && !in_q[y])
                q[++q[0]] = y, in_q[y] = 1;
        }
    }
}

void output() {
    for (int i = 4; ; --i) {
        if (ans[i] == 0) continue;
        printf("%d %d\n", i, ans[i]);
        return;
    }
}

int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);

    input();
    solve();
    output();

    return 0;
}