#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <string>
#define endl '\n'

using namespace std;

vector<int> ord;

void dfs(int v, vector<vector<int>> &g, vector<bool> &been) {
    been[v] = true;
    for (auto u : g[v]) {
        if (!been[u]) {
            dfs(u, g, been);
        }
    }
    ord.push_back(v);
}

void col(int v, int c, vector<vector<int>> &g, vector<int> &cc) {
    cc[v] = c;
    for (auto u : g[v]) {
        if (cc[u] == -1) {
            col(u, c, g, cc);
        }
    }
}

vector<int> solve(vector<vector<int>> &g) {
    int n = (int)g.size();
    vector<bool> been(n, false);
    ord.clear();
    for (int i = 0; i < n; ++i) {
        if (!been[i]) {
            dfs(i, g, been);
        }
    }
    reverse(ord.begin(), ord.end());
    vector<vector<int>> revg(n);
    for (int i = 0; i < n; ++i) {
        for (auto j : g[i]) {
            revg[j].push_back(i);
        }
    }
    vector<int> cl(n, -1);
    int c = 0;
    for (auto u : ord) {
        if (cl[u] == -1) {
            col(u, c, revg, cl);
            c++;
        }
    }
    unordered_map<int, int> d;
    int cn = 0;
    for (int i = 0; i < n; ++i) {
        if (d.find(cl[i]) == d.end()) {
            d[cl[i]] = cn;
            cn++;
        }
    }
    for (int i = 0; i < n; ++i) {
        cl[i] = d[cl[i]];
    }
    return cl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, z;
    cin >> n >> m >> z;
    int u, v;
    vector<vector<int>> g(n);
    vector<pair<int, int>> e;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        e.push_back({u, v});
    }
    vector<int> qw = solve(g);
    int ans = 0;
    int cnt = 0;
    for (int msk = 0; msk < (1 << m); ++msk) {
        int cur = 0;
        for (int i = 0; i < m; ++i) {
            cur += ((msk >> i) & 1);
        }
        if (cur < ans) {
            continue;
        }
        int var = 0;
        for (int sm = msk; sm > 0; sm = ((sm - 1) & msk)) {
            vector<vector<int>> gr(n);
            for (int i = 0; i < m; ++i) {
                if ((msk >> i) & 1) {
                    if ((sm >> i) & 1) {
                        gr[e[i].second].push_back(e[i].first);
                    } else {
                        gr[e[i].first].push_back(e[i].second);
                    }
                } else {
                    gr[e[i].first].push_back(e[i].second);
                }
            }
            vector<int> tr = solve(gr);
            if (qw == tr) {
                var++;
                if (var > 1) {
                    break;
                }
            }
        }
        if (var == 0) {
            if (cur > ans) {
                ans = cur;
                cnt = 1;
            } else if (cur == ans) {
                cnt++;
            }
        }
    }
    cout << ans << endl;
    cout << cnt << endl;
    return 0;
}
