#include <stdio.h>
#define NMAX 2020
#define MMAX 60100

int A[NMAX][NMAX], N, M, Muc[2][MMAX];

int max(int a, int b)
{
        return (a>b?a:b);
}

int main()
{
        int i, j, k, a, b, c, d, nsol4 = 0, nsol3 = 0, sol, nsol, m;

        freopen("count.in", "r", stdin);
        scanf("%d %d", &N, &M);

        for (k = 0; k < M; k++)
        {
                scanf("%d %d", &i, &j);
                if (A[i][j] == 0)
                {
                   A[i][j] = A[j][i] = 1;
                   Muc[0][k] = i; Muc[1][k] = j;
                }
        }

        for (i = 0; i < M; i++)
        {
            a = Muc[0][i]; b = Muc[1][i];
            m = max(a, b);
            for (j = 0; j < M; j++)
            {
                c = Muc[0][j]; d = Muc[1][j];
                if ((m < c && m < d) && ((A[a][c]+A[a][d]+A[b][c]+A[b][d]) == 4))
                   nsol4++;
            }
            for (j = m; j <= N; j++)
                if ((A[a][j]+A[b][j]) == 2)
                   nsol3++;
        }

        if (M == 0) sol = 1, nsol = N;
        else
        if (nsol3+nsol4 == 0)
           sol = 2, nsol = M;
        else
            if (nsol4 == 0)
               sol = 3, nsol = nsol3;
            else
                sol = 4, nsol = nsol4;

        freopen("count.out", "w", stdout);
        printf("%d %d\n", sol, nsol);

        return 0;
        
}