#include<bits/stdc++.h>
using namespace std;

int cl, timer;
vector<int> tin, up, clr, used, st, clr2;
vector<vector<int>> g;

void dfs(int v, int t) {
    st.push_back(v);
    used[v] = 1;
    tin[v] = up[v] = timer++;
    for (auto u: g[v]) {
        if (used[u]) {
            if ((t == 1 && clr[u] != -1) || (t == 2 && clr2[u] != -1)) continue;
            up[v] = min(up[v], tin[u]);
        }
        else {
            dfs(u, t);
            up[v] = min(up[v], up[u]);
            if (up[u] > tin[v]) {
                while (1) {
                    int u2 = st.back();
                    st.pop_back();
                    if (t == 1) clr[u2] = cl;
                    else clr2[u2] = cl;
                    if (u2 == u) break;
                }
                cl++;
            }
        }
    }
}

void solve() {
    int n, m, gr;
    cin >> n >> m >> gr;
    vector<array<int, 2>> a;
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        a.push_back({v, u});
        g[v].push_back(u);
    }
    tin.assign(n + 1, 0);
    up.assign(n + 1, 0);
    clr.assign(n + 1, -1);
    used.assign(n + 1, 0);
    cl = 0;
    timer = 0;
    for (int v = 1; v <= n; v++) {
        if (used[v]) continue;
        dfs(v, 1);
        while (!st.empty()) {
            clr[st.back()] = cl;
            st.pop_back();
        }
        cl++;
    }
    vector<int> f(1<<m);
    for (int mask = 1; mask < (1<<m); mask++) {
        g.assign(n + 1, {});
        tin.assign(n + 1, 0);
        up.assign(n + 1, 0);
        clr2.assign(n + 1, -1);
        used.assign(n + 1, 0);
        cl = 0;
        timer = 0;
        for (int i = 0; i < m; i++) {
            int v = a[i][0], u = a[i][1];
            if (mask&(1<<i)) {
                g[u].push_back(v);
            }
            else {
                g[v].push_back(u);
            }
        }
        for (int v = 1; v <= n; v++) {
            if (used[v]) continue;
            dfs(v, 2);
            while (!st.empty()) {
                clr2[st.back()] = cl;
                st.pop_back();
            }
            cl++;
        }
        bool flag = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (clr[i] == clr[j] && clr2[i] != clr2[j]) {
                    flag = 0;
                    break;
                }
                if (clr[i] != clr[j] && clr2[i] == clr2[j]) {
                    flag = 0;
                    break;
                }
            }
        }
        if (flag) f[mask] = 1;
    }
    for (int i = 0; i < m; i++) {
        for (int mask = 0; mask < (1<<m); mask++) {
            if (mask&(1<<i)) f[mask] += f[mask^(1<<i)];
        }
    }
    int res = 0, cnt = 1;
    for (int mask = 1; mask < (1<<m); mask++) {
        if (f[mask] != 0) continue;
        int k = 0;
        for (int i = 0; i < m; i++) {
            if (mask&(1<<i)) {
                k++;
            }
        }
        if (k > res) {
            res = k;
            cnt = 1;
        }
        else if (k == res) {
            cnt++;
        }
    }
    cout << res << '\n' << cnt;
}

int32_t main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    solve();
}
