#include <fstream>
#include <vector>
#include <deque>
#include <set>
#define DIM 30002

using namespace std;

ifstream in ("count.in");
ofstream out("count.out");

int n, m, x, y, nr3, nr4;
int nrEdg[DIM];

bool viz[DIM];

struct edgeGraph{
    int node, index;
};

set<int> graf[DIM];

struct edge{
    int x, y;
    bool viz;
};

vector<edge> edges;

vector<int> crtNode;

deque<int> q;

bool check3(int node1, int node2, int node3){
    return graf[node1].find(node2) != graf[node1].end() && graf[node1].find(node3) != graf[node1].end() && graf[node2].find(node3) != graf[node2].end();
}

bool check4(int node1, int node2, int node3, int node4){
    bool ok1, ok2, ok3, ok4, ok5, ok6;
    ok1 = graf[node1].find(node2) != graf[node1].end();
    ok2 = graf[node1].find(node3) != graf[node1].end();
    ok3 = graf[node2].find(node3) != graf[node2].end();
    ok4 = graf[node2].find(node4) != graf[node2].end();
    ok5 = graf[node3].find(node4) != graf[node3].end();
    ok6 = graf[node1].find(node4) != graf[node1].end();
    return ok1 && ok2 && ok3 && ok4 && ok5 && ok6;
}

void solve(int node){
    for(int i = 0; i < crtNode.size(); ++ i){
        for(int j = i + 1; j < crtNode.size(); ++ j){
            if(check3(node, crtNode[i], crtNode[j])){
                ++ nr3;
            }
        }
    }
    for(int i = 0; i < crtNode.size(); ++ i){
        for(int j = i + 1; j < crtNode.size(); ++ j){
            for(int k = j + 1; k < crtNode.size(); ++ k){
                if(check4(node, crtNode[i], crtNode[j], crtNode[k])){
                    ++ nr4;
                }
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    in>>n>>m;
    
    for(int i = 1; i <= m; ++ i){
        in>>x>>y;
        graf[x].insert(y);
        graf[y].insert(x);
    }
    
    for(int i = 1; i <= n; ++ i){
        if(graf[i].size() <= 5){
            q.push_back(i);
            viz[i] = true;
        }
        nrEdg[i] = graf[i].size();
    }
    
    while(!q.empty()){
        int node = q.front();
        q.pop_front();
        for(auto it : graf[node]){
            crtNode.push_back(it);
        }
        solve(node);
        
        crtNode.clear();
        for(auto it : graf[node]){
            nrEdg[it] --;
            graf[it].erase(node);
            if(nrEdg[it] <= 5 && nrEdg[it] >= 0 && viz[it] == 0){
                q.push_back(it);
                viz[it] = true;
            }
        }
        graf[node].clear();
    }
    
    int nr1 = n;
    int nr2 = m;
    if(nr4){
        out<<"4 "<<nr4;
    }
    else{
        if(nr3){
            out<<"3 "<<nr3;
        }
        else{
            if(nr2){
                out<<"2 "<<nr2;
            }
            else{
                out<<"1 "<<nr1;
            }
        }
    }
    
    return 0;
}