#include <fstream>
#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 v[nmax+1][nmax/30], size[nmax+1];

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

bool vecini( int x, int y ) {
    return (v[x][y/30]&(1<<(y%30)));
}

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 ( vector <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 ( vector <int>::iterator it= g[x].begin(); it!=g[x].end(); ++it ) {
        if ( u[*it]==0 ) {
            v[*it][x/30]-= (1<<(x%30));
            v[x][(*it)/30]-= (1<<((*it)%30));
            --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].push_back(y);
        g[y].push_back(x);
        v[x][y/30]|= (1<<(y%30));
        v[y][x/30]|= (1<<(x%30));
        ++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;
}