#include <bits/stdc++.h>
using namespace std;

ifstream in ( "count.in"  );
ofstream out( "count.out" );

const int DIM = 3e4 + 5;

set<int> gph[DIM]; deque<int> que; vector<int> lst;

int main() {
    ios::sync_with_stdio( false );
    
    int n, m;
    in >> n >> m;
    
    for( int i = 1; i <= m; i ++ ) {
        int x, y;
        in >> x >> y;
        
        gph[x].insert( y );
        gph[y].insert( x );
    }
    
    for( int i = 1; i <= n; i ++ ) {
        if( gph[i].size() <= 5 )
            que.push_back( i );
    }
    
    int ans = 2, nrm = m;
    while( !que.empty() ) {
        int x = que.front(); que.pop_front(); lst.clear();
        
        for( int y : gph[x] )
            lst.push_back( y );
        
        for( int msk = 0; msk < (1 << gph[x].size()); msk ++ ) {
            bool ok = ( ans <= __builtin_popcount( msk ) + 1 && __builtin_popcount( msk ) + 1 <= 4 );
            
            for( int axm1 = msk; axm1 != 0 && ok == true; axm1 -= ( axm1 & (-axm1) ) ) {
                int y = lst[__builtin_ffs( axm1 ) - 1];
                
                if( gph[x].find( y ) == gph[x].end() )
                    ok = false;
                
                for( int axm2 = msk; axm2 != 0 && ok == true; axm2 -= ( axm2 & (-axm2) ) ) {
                    int z = lst[__builtin_ffs( axm2 ) - 1];
                    
                    if( y != z && gph[y].find( z ) == gph[y].end() )
                        ok = false;
                }
            }
        
            if( ok == true ) {
                if( ans < __builtin_popcount( msk ) + 1 ) {
                    ans = __builtin_popcount( msk ) + 1;
                    nrm = 1;
                }
                else {
                    if( ans == __builtin_popcount( msk ) + 1 )
                        nrm ++;
                }
            }
        }
        
        gph[x].clear();
        for( int y : lst ) {
            gph[y].erase( gph[y].find( x ) );
            
            if( gph[y].size() == 5 )
                que.push_back( y );
        }
    }

    out << ans << " " << nrm << endl;
    return 0;
}