/*
6 9 0
1 2
2 3
3 4
4 5
5 6
6 1
4 6
5 3
2 1
*/

/*
10 16 0
1 2
2 1
2 5
2 3
3 4
3 7
4 5
4 10
5 6
6 1
6 3
7 8
8 3
9 4
10 5
10 9
*/

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;
const int MAXN = 2001;
vector<pair<int, int>> g[MAXN], t[MAXN];
pair<int, int> E[MAXN];

void topsort(int u, vector<char> &used, vector<int> &order) {
    used[u] = 1;
    for (auto [v, _]: g[u]) {
        if (!used[v]) {
            topsort(v, used, order);
        }
    }
    order.push_back(u);
}

void dfs(int u, int c, vector<char> &used, vector<int> &color) {
    used[u] = 1;
    color[u] = c;
    for (auto [v, _]: t[u]) {
        if (!used[v]) {
            dfs(v, c, used, color);
        }
    }
}

vector<int> find_colors(int n) {
    vector<char> used(n + 1);
    vector<int> order, color(n + 1);
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            topsort(i, used, order);
        }
    }
    used.assign(n + 1, false);
    reverse(order.begin(), order.end());
    int cnt = 1;
    for (int i: order) {
        if (!used[i]) {
            dfs(i, cnt, used, color);
            cnt++;
        }
    }
    unordered_map<int, int> repl;
    for (int i = 1; i <= n; i++) {
        if (!repl.contains(color[i])) repl[color[i]] = repl.size();
        color[i] = repl[color[i]];
    }
    return color;
}


int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, _T;
    cin >> n >> m >> _T;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        E[i] = {u, v};
        g[u].emplace_back(v, i);
        t[v].emplace_back(u, i);
    }
    vector<int> color = find_colors(n);
    vector<int> bad_masks;
    for (int mask2 = 1; mask2 < (1 << m); mask2++) {
        for (int i = 1; i <= n; i++) {
            g[i].clear(), t[i].clear();
        }
        for (int i = 0; i < m; i++) {
            auto [u, v] = E[i];
            if ((mask2 >> i) & 1) {
                t[u].emplace_back(v, 0);
                g[v].emplace_back(u, 0);
            } else {
                g[u].emplace_back(v, 0);
                t[v].emplace_back(u, 0);
            }
        }
        if (find_colors(n) == color) {
            bad_masks.push_back(mask2);
        }
    }
    mt19937 rnd(42);
    shuffle(bad_masks.begin(), bad_masks.end(), rnd);
    while (bad_masks.size() > 1000) bad_masks.pop_back();

    int mx = -1, cntmx = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        int cur = __builtin_popcount(mask);
        if (cur < mx) continue;
        bool good = true;
        for (int sm : bad_masks) {
            if ((mask & sm) == sm) {
                good = false;
                break;
            }
        }
        if (good) {
            if (cur == mx) {
                cntmx++;
            } else {
                mx = cur;
                cntmx = 1;
            }
        }
    }
    cout << mx << "\n" << cntmx;
    return 0;
}