#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

struct cmp {
    inline bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        if (a.second == b.second)
            return a.first < b.first;
        return a.second < b.second;
    }
};

const int nmax = 30001;

set<int> a[nmax];
int d[nmax];

set<pair<int, int>, cmp> sn;
int n, m;

int ans[5];

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

    scanf("%d %d", &n, &m);

    for (int i = 1, x, y; i <= m; i++) {
        scanf("%d %d", &x, &y);
        a[x].insert(y);
        d[x]++;

        a[y].insert(x);
        d[y]++;
    }

    for (int i = 1; i <= n; i++) {
        sn.insert(make_pair(i, d[i]));
    }

    for (int i = 1; i <= n; i++) {
        int x = sn.begin()->first;
        sn.erase(sn.begin());
        d[x]--;

        vector<int> v;

        for (auto& y : a[x]) {
            v.push_back(y);
        }

        ans[1]++;
        for (int i0 = 0; i0 < v.size(); i0++) {
            int A = v[i0];
            ans[2]++;
            for (int i1 = i0 + 1; i1 < v.size(); i1++) {
                int B = v[i1];
                if (a[A].find(B) != a[A].end()) {
                    ans[3]++;
                    for (int i2 = i1 + 1; i2 < v.size(); i2++) {
                        int C = v[i2];
                        if (a[A].find(C) != a[A].end() && a[B].find(C) != a[B].end()) {
                            ans[4]++;
                        }
                    }
                }
            }
        }

        for (int i = 0; i < v.size(); i++) {
            a[v[i]].erase(a[v[i]].find(x));
            sn.erase(sn.find(make_pair(v[i], d[v[i]])));
            d[v[i]]--;
            sn.insert(make_pair(v[i], d[v[i]]));
        }
    }

    for (int i = 4; i >= 1; i--) {
        if (ans[i] != 0) {
            printf("%d %d\n", i, ans[i]);
            break;
        }
    }


    return 0;
}