#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n, m, G; cin >> n >> m >> G;
    vector<vector<int>> g(n), gr(n);
    vector<pair<int, int>> edges;
    for (int i = 0; i <m ; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        edges.pb({u, v});
        g[u].pb(v); gr[v].pb(u);
    }

    vector<int> ts, used(n, 0);
    auto dfs = [&](int v, auto&&self) -> void {
        used[v] = 1;
        for (int u : g[v]) {
            if (!used[u]) self(u, self);
        }
        ts.pb(v);
    };
    for (int i = 0; i < n; i++) {
        if (!used[i]) dfs(i, dfs);
    }
    reverse(all(ts));
    used.assign(n, 0);
    vector<int> cmp(n);
    int cc = 0;
    auto dfs2 = [&](int v, auto&&self) -> void {
        used[v] = 1; cmp[v] = cc;
        for (int u : gr[v]) {
            if (!used[u]) self(u, self);
        }
    };
    for (int i : ts) {
        if (!used[i]) {
            dfs2(i, dfs2);
            cc++;
        }
    }

    vector<bool> good((1 << m), true);
    vector<int> cnumb(n);
    vector<int> ts2(n);
    int step = 1;
    for (int mask = 1; mask < (1 << m); mask++) {
        vector<vector<int>> g2(n), gr2(n);
        for (int i = 0; i < m; i++) {
            if ((mask >> i) & 1) {
                g2[edges[i].second].pb(edges[i].first);
                gr2[edges[i].first].pb(edges[i].second);
            } else {
                gr2[edges[i].second].pb(edges[i].first);
                g2[edges[i].first].pb(edges[i].second);
            }
        }   
        step++;
        int idx = 0;
        auto dfs22 = [&](int v, auto&&self) -> void {
            used[v] = step;
            for (int u : g2[v]) {
                if (used[u] != step) self(u, self);
            }
            ts2[idx++] = v;
        };
        for (int i = 0; i < n; i++) {
            if (used[i] != step) {
                dfs22(i, dfs22);
            }
        }
        
        step++;
        int CC = 0;
        auto dfs3 = [&](int v, auto&&self) -> void {
            cnumb[v] = CC;
            used[v] = step;
            for (int u : gr2[v]) {
                if (used[u] != step) self(u, self);
            }
        };
        for (int I = n - 1; I >= 0; I--) {
            int i = ts2[I];
            if (used[i] != step) {
                dfs3(i, dfs3);
                CC++;
            }
        }

        vector<int> mtch(CC, -1), mtch2(cc, -1);
        for (int i = 0; i < n; i++) {
            if (mtch2[cmp[i]] != -1 && mtch2[cmp[i]] != cnumb[i]) good[mask] =false;
            mtch2[cmp[i]] = cnumb[i];
            if (mtch[cnumb[i]] != -1 && mtch[cnumb[i]] != cmp[i]) good[mask] = false;
            mtch[cnumb[i]] = cmp[i];
        }
    }   

    vector<bool> is((1 << m));
    int bestc = 0, cases = 1;
    for (int mask = 1; mask < (1 << m); mask++) {
        int ms2 = mask;
        while (ms2) {
            int bit = __builtin_clz(ms2);
            is[mask] = is[mask] or is[mask ^ (1 << bit)];
            ms2 ^= (1 << bit);
        }
        is[mask] = is[mask] or good[mask];
        if (!is[mask]) {
            int cnt = __builtin_popcount(mask);
            if (cnt > bestc) {
                bestc = cnt; cases = 1;
            } else if (cnt == bestc) cases++;
        }
    }
    cout << bestc << '\n' << cases << '\n';
}

signed main() {
    int tt = 1;
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #else
        cin.tie(0)->sync_with_stdio(false);
    #endif  

    while (tt--) {
        solve();
    }

    return 0;
}