#include <fstream>
#include <set>
#include <vector>

using namespace std;

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

const int nmax= 30000;

bool u[nmax+1];

int n, m, sol1, sol2;
int size[nmax+1];

multiset <int> g[nmax+1];
vector <int> vec, nr;

bool vecini( int x, int y ) {
    multiset <int>::iterator it= g[x].lower_bound(y);
    if ( *it==y ) {
        return 1;
    }
    return 0;
}

void back( int x, int k ) {
    if ( x==k+1 ) {
        if ( k>sol1 ) {
            sol1= k, sol2= 0;
        }
        ++sol2;
    } else {
        int i= 0;
        if ( !nr.empty() ) {
            i= nr.back()+1;
        }
        for ( ; i<(int)vec.size(); ++i ) {
            bool ok= 1;
            for ( int j= 0; j<(int)nr.size() && ok==1; ++j ) {
                if ( vecini(vec[i], vec[nr[j]])==0 ) {
                    ok= 0;
                }
            }

            if ( ok==1 ) {
                nr.push_back(i);
                back(x+1, k);

                nr.pop_back();
            }
        }
    }
}

void dfs( int x ) {
    vec.clear();
    for ( multiset <int>::iterator it= g[x].begin(); it!=g[x].end(); ++it ) {
        if ( u[*it]==0 ) {
            vec.push_back(*it);
        }
    }

    if ( sol1<=3 ) {
        nr.clear();
        back(2, 3);
    }
    nr.clear();
    back(2, 4);

    u[x]= 1, size[x]= 0;
    for ( multiset <int>::iterator it= g[x].begin(); it!=g[x].end(); ++it ) {
        if ( u[*it]==0 ) {
            g[*it].erase(g[*it].lower_bound(x));
            --size[*it];

            if ( size[*it]<=6 ) {
                dfs(*it);
            }
        }
    }
    g[x].clear();
}

int main(  ) {
    fin>>n>>m;
    for ( int i= 1; i<=m; ++i ) {
        int x, y;
        fin>>x>>y;

        g[x].insert(y);
        g[y].insert(x);
        ++size[x], ++size[y];
    }

    sol1= 2, sol2= m;
    for ( int i= 1; i<=n; ++i ) {
        if ( size[i]<=6 ) {
            dfs(i);
        }
    }

    fout<<sol1<<" "<<sol2<<"\n";

    return 0;
}