#include <cstdio>
#include <vector>
#include <queue>
#define Nmax 30005
#define MOD 100019

using namespace std;

int v[10],st[10],sol[10],n,m,grad[Nmax],NOD;

struct el
{
    int nod,grad;
    bool operator <(const el &A) const
    {
        return grad>A.grad;
    }
};

struct ell
{
    int x,y;
};
vector <ell> H[MOD];
priority_queue <el> Q;
vector <int> L[Nmax];
bool fol[Nmax];

inline void AH(ell w)
{
    int key=(w.x*1934+w.y*189)%MOD;
    H[key].push_back(w);
}

inline bool SH(ell w)
{
    int key=(w.x*1934+w.y*189)%MOD;
    vector <ell> :: iterator it;
    for(it=H[key].begin();it!=H[key].end();++it)
        if(it->x==w.x && it->y==w.y) return true;
    return false;
}

inline bool Ok()
{
    int t[10],i,j;
    ell w;
    t[0]=0;
    for(i=1;i<=v[0];++i)
        if(st[i]) t[++t[0]]=v[i];
    t[++t[0]]=NOD;
    for(i=1;i<=t[0];++i)
        for(j=i+1;j<=t[0];++j)
        {
            w.x=t[i]; w.y=t[j];
            if(!SH(w)) return false;
        }
    return true;

}

inline void Back(int k)
{
    int i,cnt;
    if(k==v[0]+1)
    {
        for(i=1,cnt=0;i<=v[0];++i) cnt+=(st[i]==1);
        if((cnt==2 || cnt==3) && Ok()) ++sol[cnt+1];
        return;
    }
    st[k]=0; Back(k+1);
    st[k]=1; Back(k+1);
}

int main()
{
    el w,w1;
    ell q;
    int i,x,y;
    vector <int> ::iterator it;
    freopen ("count.in","r",stdin);
    freopen ("count.out","w",stdout);
    scanf("%d%d", &n,&m);
    if(n==1)
    {
        printf("1 1\n");
        return 0;
    }
    for(i=1;i<=m;++i)
    {
        scanf("%d%d", &x,&y);
        q.x=x; q.y=y; AH(q);
        q.x=y; q.y=x; AH(q);
        L[x].push_back(y);
        L[y].push_back(x);
        ++grad[x]; ++grad[y];
    }
    for(i=1;i<=n;++i)
    {
        w.nod=i; w.grad=grad[i];
        Q.push(w);
    }
    while(!Q.empty())
    {
        w=Q.top(); Q.pop(); v[0]=0;
        if(fol[w.nod]) continue;
        for(it=L[w.nod].begin();it!=L[w.nod].end();++it)
            if(!fol[*it])
            {
                v[++v[0]]=*it;
                --grad[*it];
                w1.nod=*it; w1.grad=grad[*it]; Q.push(w1);
            }
        NOD=w.nod;
        Back(1);
        fol[w.nod]=true;
    }
    if(sol[4]) printf("4 %d\n", sol[4]);
    else
        if(sol[3]) printf("3 %d\n", sol[3]);
        else printf("2 %d\n", m);
    return 0;
}