#include<fstream>
#include<set>
#include<vector>
#include<map>
#include<bitset>
#define N 30000
using namespace std;

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

vector<int> vecin[N+1];
map<pair<int,int>,bool> muchii;

set<pair<int,int> > ord;
int grad[N+1];

bitset<N+1> viz;

int ans4,ans3;

void solve(int nod){
    int i;
    vector<int> v;

    for(i=0;i<vecin[nod].size();i++)
        if (viz[vecin[nod][i]]==false) v.push_back(vecin[nod][i]);

    for(i=0;i<v.size();i++)
        for(int j=i+1;j<v.size();j++)
            if (muchii.find({v[i],v[j]})!=muchii.end()){
                ans3++;
                for(int l=j+1;l<v.size();l++)
                    if (muchii.find({v[i],v[l]})!=muchii.end() &&muchii.find({v[j],v[l]})!=muchii.end())
                        ans4++;
            }

    viz.set(nod);
    ord.erase(ord.begin());
    for(i=0;i<v.size();i++){
        muchii.erase({nod,v[i]});
        muchii.erase({v[i],nod});

        ord.erase({grad[v[i]],v[i]});
        grad[v[i]]--;
        ord.insert({grad[v[i]],v[i]});
    }
}

int main(){
    int n,m,i;
    cin>>n>>m;

    for(i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;

        vecin[a].push_back(b);
        vecin[b].push_back(a);

        muchii[{a,b}]=true;
        muchii[{b,a}]=true;

        grad[a]++;
        grad[b]++;
    }

    for(i=1;i<=n;i++)
        ord.insert({grad[i],i});

    for(i=1;i<=n;i++) solve(ord.begin()-> second);

    if (ans4>0) cout<<"4 "<<ans4;
    else
    if (ans3>0) cout<<"3 "<<ans3;
    else cout<<"2 "<<m;

    return 0;
}