#include <bits/stdc++.h>

#define int long long
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

using namespace std;

const int N = 2010;

int n, m, G;
set<int> g[N], rg[N];
bool used[N];
vector<int> topo;

void addEdge(int u, int v) {
    g[u].insert(v);
    rg[v].insert(u);
}

void delEdge(int u, int v) {
    g[u].erase(v);
    rg[v].erase(u);
}

void dfs(int v) {
    if (used[v]) {
        return;
    }
    used[v] = true;
    for (int u : g[v]) {
        dfs(u);
    }
    topo.push_back(v);
}

void dfs2(int v, int c, vector<int> &col) {
    col[v] = c;
    for (int u : rg[v]) {
        if (col[u]) {
            continue;
        }
        dfs2(u, c, col);
    }
}

void solve_case() {
    cin >> n >> m >> G;
    vector<pair<int, int>> edges;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        addEdge(u, v);
        edges.push_back({u, v});
    }
    int c = 1;
    vector<int> col(n + 1);
    {
        memset(used, false, sizeof used);
        for (int v = 1; v <= n; v++) {
            dfs(v);
        }
        reverse(all(topo));
        for (int v : topo) {
            if (!col[v]) {
                dfs2(v, c, col);
                c++;
            }
        }
    }
    vector<bool> bad(1 << m);
    for (int mask = 1; mask < (1 << m); mask++) {
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                auto [u, v] = edges[i];
                delEdge(u, v);
                addEdge(v, u);
            }
        }
        bool same = true;
        vector<int> ncol(n + 1);
        {
            memset(used, false, sizeof used);
            for (int v = 1; v <= n; v++) {
                dfs(v);
            }
            reverse(all(topo));
            vector<int> was(c);
            for (int v : topo) {
                if (!ncol[v]) {
                    if (was[col[v]]) {
                        same = false;
                        break;
                    }
                    dfs2(v, col[v], ncol);
                    was[col[v]] = true;
                } else {
                    same &= (ncol[v] == col[v]);
                }
            }
        }
        if (same) {
            bad[mask] = true;
        }
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                auto [u, v] = edges[i];
                delEdge(v, u);
                addEdge(u, v);
            }
        }
    }
    int mx = 0, cnt = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        bool ok = true;
        for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
            ok &= !bad[sub];
        }
        if (ok) {
            int cur = (int) __builtin_popcount(mask);
            if (cur > mx) {
                mx = cur;
                cnt = 0;
            }
            if (cur == mx) {
                cnt++;
            }
        }
    }
//    for (int mask = 0; mask < (1 << m); mask++) {
//        bool ok = true;
//        for (int bad : bads) {
//            if ((mask & bad) == bad) {
//                ok = false;
//                break;
//            }
//        }
//        if (ok) {
//            int cur = (int) __builtin_popcount(mask);
//            if (cur > mx) {
//                mx = cur;
//                cnt = 0;
//            }
//            if (cur == mx) {
//                cnt++;
//            }
//        }
//    }
    cout << mx << '\n';
    cout << cnt << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve_case();
    }
}