#include <bits/stdc++.h>

using namespace std;

ifstream fin("count.in");
ofstream fout("count.out");
typedef long long ll;
bool Edge[3000][3000];
map<ll,bool> Hash;
int N,M;
pair<int,int> A[30010];
const int P1 =1100379;
const int P2 =100391;
const int P3 = 100393;

ll fast_hash(int a,int b,int c){
    if (a > b)
    swap(a, b);
    if (a > c)
        swap(a, c);
    if (b > c)
        swap(b, c);
    return a*P1 + b*P2 + c*P3;

}

int cycle_3(){
    int cnt = 0;
    for (int i = 1; i <= M;i++){
        int a = A[i].first;
        int b = A[i].second;
        for (int j = 1; j  <= N;j++){
            if (j != a && j != b && Edge[j][a] && Edge[j][b]) {
                ll local_hash = fast_hash(a,b,j);
                if (!Hash[local_hash]) cnt++,Hash[local_hash] = 1;
            }
        }
    }
    return cnt;
}

int cycle_4(){
    int cnt = 0;
    for (int i = 1; i < N;i++)
    for(int j = i +1; j <= N;j++){
        int a = A[i].first;
        int b = A[i].second;
        int c = A[j].first;
        int d = A[j].second;
        if (Edge[a][c] && Edge[a][d] && Edge[b][c] && Edge[b][d]) cnt++;
    }
    return cnt/2;
}

int main(){
    fin >>N>>M;
    for (int a,b,i = 1; i <= M;i++){
        fin >> a >> b;
        Edge[a][b] = 1;
        Edge[b][a] = 1;
        A[i] = {a,b};
    }

    int k4 = cycle_4();
    if (k4){
        fout <<4<<" "<<k4;
        return 0;
    }
    int k3 = cycle_3();
    if (k3){
        fout <<3<<" "<<k3;
        return 0;
    }
    fout <<2<<" "<<M;
    return 0;
}