#include <fstream>
#include <vector>
#include <deque>
#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;
};

vector<edgeGraph> 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){
    bool ok1, ok2, ok3;
    ok1 = ok2 = ok3 = false;
    for(auto it : graf[node1]){
        if(edges[it.index].viz == true)
            continue;
        if(it.node == node2)
            ok1 = true;
        if(it.node == node3)
            ok2 = true;
    }
    for(auto it : graf[node2]){
        if(edges[it.index].viz == true)
            continue;
        if(it.node == node3)
            ok3 = true;
    }
    return ok1 && ok2 && ok3;
}

bool check4(int node1, int node2, int node3, int node4){
    bool ok1, ok2, ok3, ok4, ok5, ok6, ok7;
    ok1 = ok2 = ok3 = ok4 = ok5 = ok6 = ok7 = false;
    for(auto it : graf[node1]){
        if(edges[it.index].viz == true)
            continue;
        if(it.node == node2)
            ok1 = true;
        if(it.node == node3)
            ok2 = true;
        if(it.node == node4)
            ok3 = true;
    }
    for(auto it : graf[node2]){
        if(edges[it.index].viz == true)
            continue;
        if(it.node == node3)
            ok5 = true;
        if(it.node == node4)
            ok6 = true;
    }
    for(auto it : graf[node3]){
        if(edges[it.index].viz == true)
            continue;
        if(it.node == node4)
            ok7 = true;
    }
    return ok1 && ok2 && ok3 && ok4 && ok5 && ok6 && ok7;
}

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].push_back({y, i - 1});
        graf[y].push_back({x, i - 1});
        edges.push_back({x, y, 0});
    }
    
    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]){
            if(edges[it.index].viz == true)
                continue;
            int nextNode = it.node;
            crtNode.push_back(nextNode);
            
        }
        solve(node);
        
        crtNode.clear();
        for(auto it : graf[node]){
            edges[it.index].viz = true;
            nrEdg[it.node] --;
            if(nrEdg[it.node] <= 5 && nrEdg[it.node] >= 0 && viz[it.node] == 0){
                q.push_back(it.node);
                viz[it.node] = true;
            }
        }
    }
    
    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;
}