//#pragma GCC optimize("unroll-loops, Ofast")
//#pragma GCC target("sse,sse2,avx,avx2")

#include <bits/stdc++.h>

using namespace std;
int n, m, G;
vector<bool> used;
vector<int> tops;
vector<vector<int>> gg, gg1;

void dfs(int v) {
    used[v] = true;
    for (int to: gg[v]) {
        if (used[to])continue;
        dfs(to);
    }
    tops.push_back(v);
}

vector<int> col;

int C;

void paint(int v) {
    col[v] = C;
    for (int to: gg1[v]) {
        if (!col[to]) {
            paint(to);
        }
    }
}

vector<int> get_pain() {
    used.assign(n, false);
    tops.clear();
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs(i);
        }
    }
    col.assign(n, 0);
    reverse(tops.begin(), tops.end());
    C = 1;
    for (int to: tops) {
        if (col[to] == 0) {
            paint(to);
            C++;
        }
    }
    int Z = 1;
    vector<int> col1(n, 0);
    col1[0] = Z;
    for (int i = 1; i < n; ++i) {
        if (col[i] == col[i - 1]) {
            col1[i] = col1[i - 1];
        } else {
            Z++;
            col1[i] = Z;
        }
    }
    return col1;
}

void solve() {
    cin >> n >> m >> G;
    gg.assign(n, {}), gg1.assign(n, {});
    vector<pair<int, int>> e;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        gg[u].push_back(v);
        gg1[v].push_back(u);
        e.push_back({u, v});
    }
    vector<int> full = get_pain();
    int mx = 0;
    int cnt = 1;
    for (int i = 0; i < 1 << m; ++i) {
        if (__builtin_popcount(i) < mx)continue;
        int cn = 0;
        for (int j = i; j; j = (j - 1) & i) {
            gg.assign(n, {}), gg1.assign(n, {});
            for (int k = 0; k < m; ++k) {
                if (!(i & (1 << k))) {
                    gg[e[k].first].push_back(e[k].second);
                    gg1[e[k].second].push_back(e[k].first);
                } else {
                    if (!(j & (1 << k))) {
                        gg[e[k].first].push_back(e[k].second);
                        gg1[e[k].second].push_back(e[k].first);
                    } else {
                        gg[e[k].second].push_back(e[k].first);
                        gg1[e[k].first].push_back(e[k].second);
                    }
                }
            }
            if (get_pain() == full) {
                cn++;
                break;
            }
        }
        if (cn == 0) {
            if (mx == __builtin_popcount(i)) {
                cnt++;
            } else {
                mx = __builtin_popcount(i);
                cnt = 1;
            }
        }
    }
    cout << mx << "\n";
    cout << cnt << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}
