#include <iostream>
#include <fstream>
#define NMAX 106

using namespace std;

ifstream f("colorare.in");
ofstream g("colorare.out");

int a[NMAX][NMAX],x[NMAX],n,m,nr,maxim;

void citire()
{
    int i,x,y;
    f>>n>>m;
    for (i=1;i<=m;i++){
        f>>x>>y;
        a[x][y]=a[y][x]=1;
    }
}

int ok(int k)
{
    int i;
    for (i=1;i<k;i++){
        if(a[i][k] && x[i]==x[k])
                return 0;
    }
    return 1;
}

void greedy()
{
    int i,k=1,ok,j;
    x[1]=1;
    for (i=2;i<=n;i++)
    {
        k=1;
        do
        {
            ok=1;
            for (j=1;j<=i-1;j++)
                if(a[i][j]&&x[j]==k) {ok=0; break;}
            if(!ok) k++;
        }while (!ok);
        x[i]=k;
        if(maxim<k) maxim=k;
    }
}

void Bkt(int k)
{
    int i, rasp;
    for (i=1;i<=maxim;i++){
        x[k] = i;
        if (ok(k)){
            if (k==n){
                nr++;
            }
            else Bkt(k+1);
        }
    }
}

int main()
{
    citire();
    greedy();
    Bkt(1);
    g<<maxim<<' '<<nr;
    return 0;
}