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

using namespace std;

const int N = 30100;

int n, m, gr[N];

bool used[N];

set <int> L[N];

priority_queue <pair <int, int>, vector < pair <int, int> >, greater < pair <int, int> > > NOD;

void read() {
    int x, y;

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

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

        L[x].insert(y);
        L[y].insert(x);

        ++ gr[x];
        ++ gr[y];
    }
}

void init() {
    for (int i = 1; i <= n; ++ i)
        NOD.push(make_pair(gr[i], i));
}

void verif3(int nod, int &rc, int &nr) {
    for (set <int> :: iterator it1 = L[nod].begin(); it1 != L[nod].end(); ++ it1)
        for (set <int> :: iterator it2 = L[nod].begin(); it2 != L[nod].end(); ++ it2)
            if (*it1 != *it2 && *it1 < *it2) {
                if (L[*it1].find(*it2) != L[*it1].end()) {
                    if (rc < 3) {
                        rc = 3;
                        nr = 1;
                    } else
                        ++ nr;
                }
            }
}

void verif4(int nod, int &rc, int &nr) {
    for (set <int> :: iterator it1 = L[nod].begin(); it1 != L[nod].end(); ++ it1)
        for (set <int> :: iterator it2 = L[nod].begin(); it2 != L[nod].end(); ++ it2)
            if (*it1 < *it2)
                for (set <int> :: iterator it3 = L[nod].begin(); it3!= L[nod].end(); ++ it3)
                    if (*it1 != *it3 && *it2 != *it3 && *it2 < *it3) {
                        if (L[*it1].find(*it2) != L[*it1].end() && L[*it3].find(*it2) != L[*it3].end() && L[*it1].find(*it3) != L[*it1].end()) {
                            if (rc < 4) {
                                rc = 4;
                                nr = 1;
                            } else
                                ++ nr;
                        }
                    }
}

void sterge_vecini(int nod) {
    for (set <int> :: iterator it = L[nod].begin(); it != L[nod].end(); ++ it) {
        -- gr[*it];

        L[*it].erase(L[*it].find(nod));

        NOD.push(make_pair(gr[*it], *it));
    }
}

void solve() {
    int nc, rc = 2, nr = m;

    while ((!NOD.empty()) && NOD.top().first <= 5) {
        nc = NOD.top().second;
        NOD.pop();

        if (used[nc])
            continue;

        if (rc == 4)
            verif4(nc, rc, nr);
        else {
            verif4(nc, rc, nr);

            if (rc != 4)
                verif3(nc, rc, nr);
        }

        sterge_vecini(nc);

        used[nc] = 1;
    }

    printf("%d %d\n", rc, nr);
}

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

    read();

    init();

    solve();

    return 0;
}