#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f("colorare.in");
ofstream g("colorare.out");
int n,nr,mat[100][100],sol,c,y,m,x[100];
void afis()
{
    int maxx=0;
    for(int i=1;i<=n;i++) {g<<x[i]<<" ";
    maxx=max(maxx,x[i]);
    }
   // minn=min(maxx,minn);
    g<<endl;
}
int maxx=0;
int valid(int k)
{
    int maxx2=0;
    for(int i=1;i<k;i++)if(x[i]==x[k] && mat[i][k]) return 0;
   // for(int i=1;i<k;i++)maxx2=max(maxx2,x[i]);
    if(k>1 && x[k]>maxx+1) return 0;
    return 1;
}

void greedy()
{
    int i,k,ok,j;
    x[1]=1;
    for(i=2;i<=n;i++)
    {
        k=1;
        do
        {
            ok=1;
            for(j=1;j<i && ok;j++)
                if(mat[i][j] && x[j]==k)ok=0;
            if(!ok)k++;
        }while(!ok);
        x[i]=k;
    maxx=max(k,maxx);
    }
 //cout<<maxx<<endl;
 }
void bkt(int k)
{
    for(int i=1;i<=maxx;i++)
    {
        x[k]=i;
        if(valid(k))
        if(k==n) {sol++;/*afis();*/}
        else bkt(k+1);
    }
}
int main()
{
   f>>n>>m;
    for(int i=1;i<=m;i++){f>>c>>y; mat[c][y]=mat[y][c]=1;}
    greedy();
   bkt(1);
   g<<maxx<<" "<<sol;
    return 0;
}