#include <bits/stdc++.h>

#define MAXN 30005

int N, M;
std::set <int> ADC[MAXN];

inline void AddEdge(int X, int Y) {
    ADC[X].insert(Y);
    ADC[Y].insert(X);
}

bool Contains(int A, int B) {
    return (ADC[A].find(B) != ADC[A].end());
}
bool Check4(int A, int B, int C, int D) {
    return (Contains(A, B) && Contains(A, C) && Contains(A, D) && Contains(B, C) && Contains(B, D) && Contains(C, D));
}

bool Check3(int A, int B, int C) {
    return (Contains(A, B) && Contains(A, C) && Contains(B, C));
}

bool Check2(int A, int B) {
    return true;
}

int Count;
bool Seen[MAXN];
int Try4() {
    Count = 0;
    for (int i=1; i<=N; ++i) {
        Seen[i] = 1;
        for (auto Edge:ADC[i]) {
            Seen[Edge] = 1;
                for (auto Edge0:ADC[Edge]) if (!Seen[Edge0]) {
                    Seen[Edge0] = 1;
                    for (auto Edge1:ADC[Edge0]) if (!Seen[Edge1]) {
                        Count += Check4(i, Edge, Edge0, Edge1);
                    }   Seen[Edge0] = 0;
                }   Seen[Edge] = 0;
        }   Seen[i] = 0;
    }   return Count;
}

int Try3() {
    Count = 0;
    for (int i=1; i<=N; ++i) {
        Seen[i] = 1;
        for (auto Edge:ADC[i]) {
            Seen[Edge] = 1;
                for (auto Edge0:ADC[Edge]) if (!Seen[Edge0]) {
                    Count += Check3(i, Edge, Edge0);
                }   Seen[Edge] = 0;
        }   Seen[i] = 0;
    }   return Count;
}

int Try2() {
    Count = 0;
    for (int i=1; i<=N; ++i) {
        Seen[i] = 1;
        for (auto Edge:ADC[i]) {
            Count += Check2(i, Edge);
        }   Seen[i] = 0;
    }   return Count;
}

std::ifstream In ("count.in");
std::ofstream Out("count.out");

void Citire() {
    In >> N >> M;
    for (int i=1, X, Y; i<=M; ++i)
        In >> X >> Y, AddEdge(X, Y);
}

void Rezolvare() {
    if (Try4())
        Out << 4 << ' ' << Count/24 << '\n';
    else if (Try3())
        Out << 3 << ' ' << Count/6 << '\n';
    else if (Try2())
        Out << 2 << ' ' << Count/2 << '\n';
    else
        Out << 1 << ' ' << N << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}