#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#define N 30000

using namespace std;

vector < int > muc [ N ];
int comp [ 5 ];
int grad [ N ];
int viz [ N ];


vector < int > ::iterator it1 ;
int nrsol  ;
int fin ;

void back4 ( int nod , int k ){
    static int nrvec , i ;
    vector < int > ::iterator it ;

    if ( k == fin ){
        nrsol ++ ;
        return ;

    }



    comp [ k ] = nod ;

    for ( it = muc[ nod ].begin() ; it!= muc[ nod ].end() ; it ++ ){

        if ( viz [ *it ] ){
            continue ;
        }
        if ( *it < nod && k >= 2 ){
            continue ;
        }

        nrvec = 0 ;
        for (  it1 = muc [ *it ].begin ( ) ; it1 != muc [ *it ].end() ; it1++ ){
            for ( i = 1 ; i <= k ; i++ ){
                if ( *it1 == comp [ i ] ){
                    nrvec ++ ;
                }
            }
        }
        if ( nrvec - k ){
            continue ;
        }

        back4 ( *it , k + 1 );



    }




}

int main(){
    int n , m , i ;
    int x ,y ;

    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);

    scanf("%d%d",&n,&m);

    for ( i = 0 ; i < m ; i++ ){
        scanf("%d%d",&x,&y);

        muc[ x ].push_back( y );
        muc[ y ].push_back( x );

        grad [ x ] ++ ;
        grad [ y ] ++ ;

    }

    int nrnod = n ;
    fin = 4 ;
    while ( nrnod ){

        for ( i = 1 ; i <= n ; i ++){
            if ( grad [ i ] < 6 ){

                back4 ( i , 1 );
                viz [ i ] = -1 ;
                for  ( it1 = muc[ i ].begin() ; it1 != muc[ i ].end() ; it1++ ){
                    grad [ *it1 ] -- ;
                }
                nrnod -- ;
            }
        }

    }

    if ( nrsol ){
        printf("4 %d",nrsol);
        return 0 ;
    }

    nrnod = n ;
    memset ( viz , 0 , sizeof ( viz ) );
    for ( i = 1 ; i <= n ; i ++ ){
        grad[ i ] = muc[ i ].size();
    }
    fin = 3 ;

    while ( nrnod ){

        for ( i = 1 ; i <= n ; i ++){
            if ( grad [ i ] < 6 ){

                back4 ( i , 1 );
                viz [ i ] = -1 ;
                for  ( it1 = muc[ i ].begin() ; it1 != muc[ i ].end() ; it1++ ){
                    grad [ *it1 ] -- ;
                }
                nrnod -- ;
            }
        }

    }

    if ( nrsol  ){
        printf("3 %d",nrsol );
        return 0;
    }


    memset ( viz , 0 , sizeof ( viz ) );

    for ( i = 1 ; i <= n ; i ++ ){
        for ( it1 = muc [ i ].begin ( ) ; it1 != muc[ i ].end( ) ; it1 ++ ){
            if ( viz [ *it1 ] ){
                nrsol ++ ;
            }
        }
        viz [ i ] = -1 ;
    }


    printf("2 %d",nrsol);

    return 0;
}