# include <cstdio>
# include <ext/hash_set>
# include <vector>
using namespace std;
using namespace __gnu_cxx ;

const char *FIN = "count.in", *FOU = "count.out";
const int MAX = 30005;

int N, M, sol[2];
hash_set <int> G[MAX];
vector <int> E;

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d %d", &N, &M);
    for (int i = 1, x, y; i <= M; ++i) {
        scanf ("%d %d", &x, &y);
        G[x].insert (y);
        G[y].insert (x);
    }
    for (int i = 1; i <= N; ++i)
        if (G[i].size () < 6)
            E.push_back (i);
    for (vector <int> :: iterator it = E.begin (); it != E.end (); ++it) {
        for (hash_set <int> :: iterator i = G[*it].begin (); i != G[*it].end (); ++i)
            for (hash_set <int> :: iterator j = i; j != G[*it].end (); ++j)
                if (*j > *i && G[*j].count (*i) > 0) {
                    ++sol[0];
                    for (hash_set <int> :: iterator k = j; k != G[*it].end (); ++k)
                        if (*k > *j && G[*k].count (*i) > 0 && G[*k].count (*j) > 0)
                            ++sol[1];
                }
        for (hash_set <int> :: iterator i = G[*it].begin (); i != G[*it].end (); ++i) {
            G[*i].erase (*it);
            if (G[*i].size () == 5)
                E.push_back (*i);
        }
    }
    if (sol[1]) fprintf (fopen (FOU, "w"), "4 %d", sol[1]);
    else if (sol[0]) fprintf (fopen (FOU, "w"), "3 %d", sol[0]);
    else fprintf (fopen (FOU, "w"), "2 %d", M);
}