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

using namespace std;

const int nmax = 3e4 + 10;
const int mod = 131071;
const int p = 17;

int ans[5];

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

pair < int, int > ap[2][mod+1];
vector < int > g[nmax];

int nxt(int pos) {
    return (pos * 5 + 1) & mod;
}

void add(int x, int y) {
    g[x].push_back(y);

    bool idx = (x > y);
    int pos; for (pos = ((x & mod) * p) & mod; ap[idx][pos] != make_pair(0, 0); pos = nxt(pos));
    ap[idx][pos] = {x, y};
}

void del(int x, int y) {
    for (int node = 0; node < g[x].size(); ++node)
        if (g[x][node] == y) {
            swap(g[x][node], g[x].back());
            g[x].pop_back();
        }

    bool idx = (x > y);
    int pos; for (pos = ((x & mod) * p) & mod; ap[idx][pos] != make_pair(0, 0) && ap[idx][pos] != make_pair(x, y); pos = nxt(pos));
    if (ap[idx][pos] != make_pair(0, 0)) ap[idx][pos] = {-1, -1};
}

bool is(int x, int y) {
    bool idx = (x > y);
    int pos; for (pos = ((x & mod) * p) & mod; ap[idx][pos] != make_pair(0, 0) && ap[idx][pos] != make_pair(x, y); pos = nxt(pos));
    return (ap[idx][pos] == make_pair(x, y));
}

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

        add(x, y); add(y, 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]++;
            for (auto z = y + 1; z != g[x].end(); ++z) {
                if (!is(*z, *y)) continue;
                ans[3]++;
                for (auto w = z + 1; w != g[x].end(); ++w) {
                    if (!is(*w, *y) || !is(*w, *z)) continue;
                    ans[4]++;
                }
            }
        }

        for (auto y : g[x]) {
            del(y, 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;
}