#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

vector <int> g[30000];
map <int,int> a;
int n,g6[30000],vis[5],l,r,sol[5];

inline int nr()
{
    return vis[0]+vis[1]+vis[2]+vis[3]+vis[4];
}

void back(int aux)
{
    if (aux==g[g6[l]].size())
    {
        if (nr()>1&&nr()<4)
        {
            int i,j;
            for (i=1;i<5;++i)
                if (vis[i])
                    for (j=0;j<i;++j)
                        if (vis[j])
                            if (!a[g[g6[l]][i]*n+g[g6[l]][j]])
                                return;
            ++sol[nr()+1];
        }
        return;
    }
    back(aux+1);
    vis[aux]=1;
    back(aux+1);
    vis[aux]=0;
}

int main()
{
    int i,m,x,x2,y;
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (i=1;i<=m;++i)
    {
        scanf("%d %d\n",&x,&y);
        --x;
        --y;
        g[x].push_back(y);
        g[y].push_back(x);
        a[x*n+y]=g[x].size();
        a[y*n+x]=g[y].size();
    }
    for (i=0;i<n;++i)
        if (g[i].size()<6)
        {
            g6[r]=i;
            ++r;
        }
    for (l=0;l<r;++l)
    {
        back(0);
        for (i=0;i<g[g6[l]].size();++i)
        {
            x=g[g6[l]][i];
            x2=g[x][g[x].size()-1];
            g[x][a[x*n+g6[l]]-1]=x2;
            a[x*n+x2]=a[x*n+g6[l]];
            g[x].pop_back();
            if (g[x].size()==5)
            {
                g6[r]=x;
                ++r;
            }
        }
    }
    if (sol[4])
        printf("4 %d",sol[4]);
    else if (sol[3])
        printf("3 %d",sol[3]);
    else
        printf("2 %d",sol[2]);
    return 0;
}