#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
const ll inf = 1e17 + 7;
ll col = 0;
vector<vector<ll>> comp;
vector<ll> color;
void kraska(ll v, vector<vector<ll>> &g) {
    color[v] = col;
    comp[col].push_back(v);
    for(auto u : g[v]) {
        if (!color[u]) {
            kraska(u, g);
        }
    }
}

void dfs(ll v, ll p, vector<ll> &used, vector<ll> &h, vector<ll> &up, vector<vector<ll>> &g) {
    used[v] = 1;
    up[v] = h[v];
    for(auto u : g[v]) {
        if (u == p) continue;
        if (used[u]) {
            up[v] = min(up[v], up[u]);
        } else {
            h[u] = h[v] + 1;
            dfs(u, v, used, h, up, g);
            up[v] = min(up[v], up[u]);
            if (up[u] > h[v] && !color[u]) {
                col++;
                kraska(u, g);
            }
        }
    }
}

void solve() {
    ll n, m, G;
    cin >> n >> m >> G;
    vector<pair<ll, ll>> p(m);
    vector<vector<ll>> g(n), gr(n);
    for(int i = 0; i < m; ++i) {
        cin >> p[i].fi >> p[i].se;
        p[i].fi--, p[i].se--;
        gr[p[i].fi].push_back(p[i].se);
    }
    vector<ll> used(n), h(n), up(n);
    color.resize(n);
    comp.resize(n + 1);
    dfs(0, -1, used, h, up, gr);
    vector<vector<ll>> comp1 = comp;
    ll mx = -1, cnt = 0;
    for(int i = 0; i < (1 << m); ++i) {
        ll ch = 0;
        for(int j = 0; j < n; ++j) {
            g[j].clear();
            comp[j].clear();
        }
        comp[n].clear();
        color.assign(n, 0);
        up.assign(n, 0);
        used.assign(n, 0);
        col = 0;
        for(int j = 0; j < m; ++j) {
            if ((i >> j) & 1) {
                ch++;
                g[p[j].fi].push_back(p[j].se);
                g[p[j].se].push_back(p[j].fi);
            } else {
                g[p[j].fi].push_back(p[j].se);
            }
        }
        if (ch >= mx) {
            dfs(0, -1, used, h, up, g);
            if (comp == comp1) {
                if (ch == mx) {
                    cnt++;
                } else {
                    mx = ch, cnt = 1;
                }
            }
        }
    }
    cout << mx << '\n';
    cout << cnt << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll T = 1;
    //cin >> T;
    while(T--) {
        solve();
        cout << '\n';
    }
    return 0;
}
