#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> g[30005];
bool viz[30005];
queue<int> q;
int bs(int st, int dr, int val, int ind)
{
    int med;
    while(st<=dr){
        med=(st+dr)/2;
        if(g[ind][med]==val){
            return med;
        }
        else{
            if(g[ind][med]>val)
                dr=med-1;
            else
                st=med+1;
        }
    }
    return -1;
}
int main()
{   freopen("count.in", "r", stdin);
    freopen("count.out", "w", stdout);
    int n,m,i,x,y,j,l,nr4=0,nr3=0;
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(i=1; i<=n; i++){
        sort(g[i].begin(), g[i].end());
        if(g[i].size()<6){
            q.push(i);
            viz[i]=1;
        }
    }
    while(!q.empty()){
        int u=q.front();
        for(i=0; i<g[u].size(); i++)
            for(j=i+1; j<g[u].size(); j++)
                for(l=j+1; l<g[u].size(); l++)
                    if(bs(0, g[g[u][j]].size()-1, g[u][i], g[u][j])!=-1 && bs(0, g[g[u][l]].size()-1, g[u][i], g[u][l])!=-1 && bs(0, g[g[u][l]].size()-1, g[u][j], g[u][l])!=-1)
                        nr4++;
        for(i=0; i<g[u].size(); i++)
            for(j=i+1; j<g[u].size(); j++)
                if(bs(0, g[g[u][j]].size()-1, g[u][i], g[u][j])!=-1)
                    nr3++;
        for(i=0; i<g[u].size(); i++){
            g[g[u][i]].erase(g[g[u][i]].begin()+bs(0, g[g[u][i]].size()-1, u, g[u][i]));
            if(g[g[u][i]].size()<6 && viz[g[u][i]]==0){
                q.push(g[u][i]);
                viz[g[u][i]]=1;
            }
        }
        q.pop();
    }
    if(nr4>0)
        printf("4 %d", nr4);
    else{
        if(nr3>0)
            printf("3 %d", nr3);
        else
            printf("2 %d", m);
    }
    return 0;
}