/*
    Advanced Algorithms - Homework 2
    Team: Yunus Inan, Nihal Ezgi Yuceturk, Mammad Hajili
*/
#include <bits/stdc++.h>
using namespace std;
vector<int> parent, rnk;
int find_parent(int node)
{
    if (parent[node] == -1)
        return node;
    return find_parent(parent[node]);
}
void union_find(int x, int y)
{
    int px = find_parent(x);
    int py = find_parent(y);
    if(rnk[px] < rnk[py]) parent[px] = py;
    else if(rnk[px] > rnk[py]) parent[py] = px;
    else{
       parent[py] = px;
       rnk[px] ++;
    }
}

vector<pair<int, int>> edges;
set< set<int> > S;
int n, m;
pair<int, set<int> > min_cut() {

    int n_vertices = n;
    set<int> contracts;
    while (n_vertices > 2)  {
        int ind = rand();
        ind = ind % m;
        int p1 = find_parent(edges[ind].first);
        int p2 = find_parent(edges[ind].second);
        if (p1 == p2) continue;
        else {
            n_vertices--;
            union_find(p1, p2);
        }
    }
    int cut = 0;
    for (int j = 0; j < m; ++ j) {
        int p1 = find_parent(edges[j].first);
        int p2 = find_parent(edges[j].second);
        if (p1 != p2) {
            contracts.insert(j);
            cut ++;
        }
    }

    return {cut, contracts};
}
int main() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin >> n >> m;
    for(int i = 0; i < m; ++ i) {
        int u, v;
        cin >> u >> v;
        u --;
        v --;
        edges.push_back({u, v});
    }
    int mn_cut = INT_MAX;

    for(int i = 0; i < 150000; ++ i) {
        parent = vector<int>(n, -1);
        rnk = vector<int>(n, 0);
        auto cut = min_cut();
        mn_cut = min(mn_cut, cut.first);
    }

    int sz = 0;
    for(int i = 0; i < 500000; ++ i)  {
        parent = vector<int>(n, -1);
        rnk = vector<int>(n, 0);
        auto cut = min_cut();

        if(cut.first == mn_cut) {
            S.insert(cut.second);
        }

        if(i % 10000 == 0 and i != 0) {
            if(sz == S.size()) break;
            sz = S.size();
        }
    }
    cout << mn_cut << " " << S.size() << endl;
}