#include <cstdio>
#include <cstring>
#include <unordered_set>
#include <vector>
#include <queue>

using namespace std;

const int N = 30003;

class MyComp {
public:
    bool operator () (const pair <int, int> &A, const pair <int, int> &B) {
        return A.first > B.first;
    }
};

vector <int> graph [N];
unordered_set <int> edge [N];
int grad [N], grad2 [N];
priority_queue <int, vector <pair <int, int> >, MyComp > pq;
bool used [N];

void initialize (const int &n) {
    int i;

    memset (used, 0, sizeof (used));
    memcpy (grad2, grad, sizeof (grad));
    for (i = 1; i <= n; i ++)
        pq.push (make_pair (i, grad [i]));
}

int main () {
    int n, m, x, y, nod, g, i, j, k, l, num, A, B, C;

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

    scanf ("%d%d", &n, &m);
    for (i = 1; i <= m; i ++) {
        scanf ("%d%d", &x, &y);
        grad [x] ++; grad [y] ++;
        graph [x].push_back (y); graph [y].push_back (x);
        edge [x].insert (y); edge [y].insert (x);
    }
    x = 2; y = m;
    for (i = 3; i <= 4; i ++) {
        initialize (n);
        num = 0;
        while (!pq.empty ()) {
            nod = pq.top ().first;
            g = pq.top ().second;
            pq.pop ();
            if (used [nod])
                continue;
            used [nod] = 1;
            for (j = 0; j < graph [nod].size (); ++ j)
                if (!used [graph [nod][j]]) {
                    A= graph [nod][j];
                    for (k = j + 1; k < graph [nod].size (); ++ k)
                        if (!used [graph [nod][k]]) {
                            B = graph [nod][k];
                            if (i == 4) {
                                for (l = k + 1; l < graph [nod].size (); ++ l) {
                                    C = graph [nod][l];
                                    if (!used [C] && edge [A].find (B) != edge [A].end () && edge [A].find (C) != edge [A].end () && edge [B].find (C) != edge [B].end ())
                                        num ++;
                                }
                            }
                            else {
                                if (edge [A].find (B) != edge [A].end ())
                                    num ++;
                            }
                        }
                }
            if (num) {
                x = i;
                y = num;
            }
            for (j = 0; j < graph [nod].size (); ++ j) {
                grad2 [graph [nod][j]] --;
                pq.push (make_pair (graph [nod][j], grad2 [graph [nod][j]]));
            }
        }
    }
    printf ("%d %d\n", x, y);
    return 0;
}