#include<algorithm>
#include<set>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int deg[30005];
vector<int> G[30005];
int in_set[30005];
set< pair<int,int> > Edges;
int Clique3,Clique4;
class CompInt
{
    public: inline bool operator()(const int &a,const int &b) const
    {
        return deg[a]<deg[b];
    };
};
multiset<int,CompInt> S;
inline bool IsClique3(int a,int b,int c)
{
    return Edges.count(make_pair(a,b)) &&
           Edges.count(make_pair(a,c)) &&
           Edges.count(make_pair(b,c));
}
inline bool IsClique4(int a,int b,int c,int d)
{
    return Edges.count(make_pair(a,b)) &&
           Edges.count(make_pair(a,c)) &&
           Edges.count(make_pair(a,d)) &&
           Edges.count(make_pair(b,c)) &&
           Edges.count(make_pair(b,d)) &&
           Edges.count(make_pair(c,d));
}
void CountCliques3(const vector<int> &v)
{
    for(int i=0;i+2<(int)v.size();i++)
        for(int j=i+1;j+1<(int)v.size();j++)
            for(int k=j+1;k<(int)v.size();k++)
                if(IsClique3(v[i],v[j],v[k]))
                    Clique3++;
}
void CountCliques4(const vector<int> &v)
{
    for(int i=0;i+3<(int)v.size();i++)
        for(int j=i+1;j+2<(int)v.size();j++)
            for(int k=j+1;k+1<(int)v.size();k++)
                for(int l=k+1;l<(int)v.size();l++)
                    if(IsClique4(v[i],v[j],v[k],v[l]))
                        Clique4++;
}
void FindCliques()
{
    if(S.size()<=2)
        return;
    int u=*S.begin();S.erase(S.begin());
    in_set[u]=0;
    vector<int> v(1,u);
    for(vector<int>::iterator it=G[u].begin();it!=G[u].end();it++)
        if(in_set[*it])
            v.push_back(*it);
    CountCliques3(v);
    CountCliques4(v);
    for(vector<int>::iterator it=G[u].begin();it!=G[u].end();it++)
        if(in_set[*it])
        {
            S.erase(*it);
            deg[*it]--;
            S.insert(*it);
        }
    FindCliques();
}
int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int x,y,i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        deg[x]++;deg[y]++;
        G[x].push_back(y);
        G[y].push_back(x);
        Edges.insert(make_pair(x,y));
        Edges.insert(make_pair(y,x));
    }
    for(int i=1;i<=n;i++)
        S.insert(i),
        in_set[i]=1;
    FindCliques();
    if(Clique4)
        printf("4 %d\n",Clique4);
    else
        if(Clique3)
            printf("3 %d\n",Clique3);
        else
            printf("2 %d\n",m);
    return 0;
}