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

main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m, g;
    cin >> n >> m >> g;
    vector < vector < int > > G(n);
    vector < pair < int , int > > ve;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; u--; v--;
        G[u].push_back(v);
        ve.push_back({u, v});
    }
    function < vector < int > (vector < vector < int > > &) > css = [&](vector < vector < int > > &G) {
        vector < vector < int > > Gr(n);
        for (int i = 0; i < n; i++)
            for (auto u : G[i]) Gr[u].push_back(i);

        vector < int > cl(n, -1), top;
        vector < bool > mark(n);
        function < void(int) > dfs1 = [&](int v) {
            mark[v] = 1;
            for (auto u : G[v])
                if (!mark[u]) dfs1(u);
            top.push_back(v);
        };
        int T = -1;
        function < void(int) > dfs2 = [&](int v) {
            cl[v] = T;
            for (auto u : Gr[v])
                if (cl[u] == -1) dfs2(u);
        };
        for (int i = 0; i < n; i++) if (!mark[i]) dfs1(i);
        reverse(begin(top), end(top));
        for (auto i : top) if (cl[i] == -1) {
            T++;
            dfs2(i);
        }

        vector < vector < int > > ps(T + 1);
        for (int i = 0; i < n; i++) ps[cl[i]].push_back(i);
        vector < int > color(n, -1);
        T = 0;
        for (int i = 0; i < n; i++) {
            if (color[i] != -1) continue;
            int tp = cl[i];
            mark[tp] = 1;
            for (auto u : ps[tp]) color[u] = T;
            T++;
        }
        return color;
    };

    vector < int > color = css(G);

    int mx = 0, ans = 0;

    for (int msk = 0; msk < (1 << m); msk++) {
        int cur = __builtin_popcount(msk);
        if (cur < mx) continue;
        int k = 1;
        for (int sub = msk; sub; sub = ((sub - 1) & msk)) {
            for (int i = 0; i < m; i++) if ((sub >> i) & 1) swap(ve[i].first, ve[i].second);
            for (int i = 0; i < n; i++) G[i].clear();
            for (auto [u, v] : ve) G[u].push_back(v);
            vector < int > cl = css(G);
            if (cl == color) k++;
            for (int i = 0; i < m; i++) if ((sub >> i) & 1) swap(ve[i].first, ve[i].second);
            if (k == 2) break;
        }
        if (k != 1) continue;
        if (cur > mx) {
            mx = cur;
            ans = 0;
        }
        if (cur == mx) ans++;
    }
    cout << mx << '\n' << ans;
}

