#include <bits/stdc++.h>

#define MAXN 30005

int N, M, Degree[MAXN], Count[5];
std::set <int> ADC[MAXN];
std::queue <int> Q;

inline void AddEdge(int X, int Y) {
    ADC[X].insert(Y);
    ADC[Y].insert(X);
    ++ Degree[X], ++ Degree[Y];
}

bool Contains(int X, int Y) {
    return (X != Y) && (ADC[X].find(Y) != ADC[X].end());
}

std::ifstream In ("count.in");
std::ofstream Out("count.out");

void Citire() {
    In >> N >> M;
    for (int i=1, X, Y; i<=M; ++i)
        In >> X >> Y, AddEdge(X, Y);
}

void Rezolvare() {
    for (int i=1; i<=N; ++i)
        if (Degree[i] <= 5)
            Q.push(i);

    int Front;
    std::set <int>::iterator it, it0, it1;
    while (!Q.empty()) {
        Front = Q.front();
        Q.pop();

        for (it = ADC[Front].begin(); it != ADC[Front].end(); ++it)
            for (it0 = it; it0 != ADC[Front].end(); ++it0)
                if (Contains(*it, *it0))
                    for (it1 = it0, Count[3]++; it1 != ADC[Front].end(); ++it1)
                        if (Contains(*it, *it1) && Contains(*it0, *it1))
                            Count[4]++;

        for (it = ADC[Front].begin(); it != ADC[Front].end(); ++it) {
            ADC[*it].erase(Front);
            -- Degree[*it];
            if (Degree[*it] == 5)
                Q.push(*it);
        }
    }   Out << (Count[4] ? 4 : (Count[3] ? 3 : 2)) << ' ' << (Count[4] ? Count[4] : (Count[3] ? Count[3] : M)) << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}