#include<stdio.h>
using namespace std;

int nrsol,a[200][200],x[200],n,m,kmax=1;

FILE*f=fopen("colorare.in","r");
FILE*g=fopen("colorare.out","w");

void citire() {
    int x,y,i;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++) {
        fscanf(f,"%d%d",&x,&y);
        a[x][y]=a[y][x]=1;
    }
}

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

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

void bkt(int k) {
    int i;
    for(i=1;i<=kmax;i++) {
        x[k]=i;
        if(verif(k)) {
            if(k==n) nrsol++;
            else bkt(k+1);
        }
    }
}

int main() {

    citire();
    greedy();
    bkt(1);

    fprintf(g,"%d %d",kmax,nrsol);

    fclose(f); fclose(g);

    return 0;
}