//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct scc {
    vector<vector<int>> g, rg;
    vector<int> used, ts;
    int T = 0, n;

    scc(int _n) : n(_n) {
        g.resize(n);
        rg.resize(n);
        used.resize(n, 0);
    }

    void add_edge(int u, int v) {
        g[u].push_back(v);
        rg[v].push_back(u);
    }

    void dfs1(int u) {
        used[u] = 1;
        for (auto to : g[u]) {
            if (!used[to]) {
                dfs1(to);
            }
        }
        ts.push_back(u);
    }

    void dfs2(int u) {
        for (auto to : rg[u]) {
            if (used[to] == -1) {
                used[to] = used[u];
                dfs2(to);
            }
        }
    }

    vector<int> build() {
        for (int i = 0; i < n; ++i) {
            if (!used[i]) {
                dfs1(i);
            }
        }
        reverse(ts.begin(), ts.end());
        fill(used.begin(), used.end(), -1);
        for (auto x : ts) {
            if (used[x] == -1) {
                used[x] = T++;
                dfs2(x);
            }
        }
        int cur = 0;
        vector<int> nx(T, -1);
        for (int i = 0; i < n; ++i) {
            int comp = used[i];
            assert(comp > -1);
            if (nx[comp] == -1) nx[comp] = cur++;
        }
        for (auto& x : used) x = nx[x];
        return used;
    }
};

signed main(int32_t argc, char* argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, g;
    cin >> n >> m >> g;
    vector<pair<int, int>> e(m);
    scc flex(n);
    for (auto& [u, v] : e) {
        cin >> u >> v;
        --u, --v;
        flex.add_edge(u, v);
    }
    auto tmp = flex.build();
    const int sz = (1 << m);
    vector<int> good(sz);
    for (int msk = 1; msk < sz; ++msk) {
        scc cur(n);
        for (int i = 0; i < m; ++i) {
            auto [u, v] = e[i];
            if (msk >> i & 1) {
                cur.add_edge(v, u);
            } else {
                cur.add_edge(u, v);
            }
        }
        good[msk] = (tmp == cur.build());
    }
    int ans = 0, cnt = 1;
    for (int msk = 1; msk < sz; ++msk) {
        int c = 1;
        for (int sub = msk; sub; sub = (sub - 1) & msk) {
            c += good[sub];
        }
        if (c == 1) {
            int cur = __builtin_popcount(msk);
            if (ans < cur) {
                ans = cur;
                cnt = 0;
            }
            if (ans == cur) cnt++;
        }
    }
    cout << ans << '\n' << cnt;
}

/*
5 6 0
1 2 1 -
1 5 2 - +
2 3 4
3 4 8 +
3 5 16 -
4 2 32 +
*/