#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

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

const int NMAX=3e4+5;
bool viz[NMAX];
set<int>v[NMAX];
queue<int>q;

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    int n,m,i,j,kon=0,kon2=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        v[x].insert(y);
        v[y].insert(x);
    }
    ///un graf planar are un nod cu degree <6
    for(i=1;i<=n;i++)
    {
        if(v[i].size()<6)
        {
            viz[i]=true;
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int p=q.front();
        q.pop();
        for(auto node1=v[p].begin();node1!=v[p].end();node1++)
        {
            for(auto node2=node1;node2!=v[p].end();node2++)
            {
                if(v[*node1].find(*node2)!=v[*node1].end())
                {
                    kon2++;
                    for(auto node3=node2;node3!=v[p].end();node3++)
                    {
                        if(v[*node1].find(*node3)!=v[*node1].end() && v[*node2].find(*node3)!=v[*node2].end())
                            kon++;
                    }
                }
            }
        }
        for(auto node1=v[p].begin();node1!=v[p].end();node1++)
        {
            v[*node1].erase(v[*node1].find(p));
            if(v[*node1].size()<6 && !viz[*node1])
            {
                viz[*node1]=true;
                q.push(*node1);
            }
        }
    }
    ///un graf planar se poate colora cu 4 culori
    if(kon)
    {
        fout<<4<<" "<<kon;
        return 0;
    }
    if(kon2)
    {
        fout<<3<<" "<<kon2;
        return 0;
    }
    fout<<2<<" "<<m;
    fin.close();
    fout.close();
    return 0;
}