#include <fstream>
#include <tr1/unordered_set>
#include <queue>

using namespace std;
using namespace tr1;

#define IT unordered_set<int> :: iterator

const int MAX_N = 30000 + 1;
const int MAX_M = 2 * MAX_N;

int n, m;

unordered_set<int> G[MAX_N];



int s3, s4;

queue<int> Q;

void deconnect(const int node) {
    for(IT it = G[node].begin() ; it != G[node].end() ; it++) {
        const int son = *it;
        G[son].erase(node);
        if(G[son].size() <= 6)
            Q.push(son);
    }
    G[node].clear();
}

bool connected(const int a, const int b){
    return G[a].count(b);
}

void check(const int node) {
    IT i1, i2, i3;
    IT b = G[node].begin(),
       e = G[node].end();

    for(i1 = b ; i1 != e ; ++i1) {
        i2 = i1;
        for(i2++ ; i2 != e ; ++i2) {
            i3 = i2;

            if(!connected(*i1, *i2))
                continue;

            ++s3;

            for(i3++ ; i3 != e ; ++i3) {
                if(connected(*i1, *i3) &&
                   connected(*i2, *i3))
                   ++s4;
            }
        }
    }
}

void DFS() {
    while(!Q.empty()) {
        const int node = Q.front();
        Q.pop();
        check(node);
        deconnect(node);
    }
}

int main() {
    ifstream in("count.in");
    in >> n >> m;
    int a, b;
    for(int i = 1 ; i <= m ; ++i) {
        in >> a >> b;
        G[a].insert(b);
        G[b].insert(a);
    }
    in.close();

    for(int i = 1 ; i <= n ; ++i)
        if(G[i].size() <= 6)
            Q.push(i);

    DFS();

    ofstream out("count.out");
    if(s4) {
        out << 4 << " " << s4 << "\n";
    } else if(s3) {
        out << 3 << " " << s3 << "\n";
    } else {
        out << 2 << " " << m << "\n";
    }

    return 0;
}