#include<algorithm>
#include<set>
#include<vector>
#include<cstdio>
#include<cassert>
#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;
struct Nod
{
    int u,deg;
    Nod() {}
    Nod(int uu,int ddeg) {u=uu;deg=ddeg;}
    inline bool operator<(const Nod &other) const
    {
        if(deg==other.deg) return u<other.u;
        return deg<other.deg;
    }
};
multiset<Nod> 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++;
}
int number;
void print()
{
    for(set<Nod>::iterator it=S.begin();it!=S.end();it++)
        fprintf(stderr,"%d %d\n",it->u,it->deg);
    fprintf(stderr,"\n");
}
void FindCliques()
{
    if(number<=2)
        return;
    int u=S.begin()->u;S.erase(S.find(Nod(u,deg[u])));
    deg[u]=0;
    in_set[u]=0;number--;
    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])
        {
            Nod p(*it,deg[*it]);
            ///if(*it==5)
            ///    fprintf(stderr,"\n\n%d %d : %d %d\n\n",*it,deg[*it],S.find(p)->u,S.find(p)->deg);
            ///assert(S.find(p)->u==*it);
            ///if(*it==5)
            ///    print();
            S.erase(S.find(p));
            ///if(*it==5)
            ///    print();
            p.deg--;deg[*it]--;
            S.insert(p);
            ///print();
        }
    FindCliques();
}
int main()
{
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);number=n;
    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(Nod(i,deg[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;
}