#include<bits/stdc++.h>

using namespace std;

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

#define int long long
// vector<vector<int>> ed;
vector<vector<int>> g, t_g;
vector<int> t_s, color, used;
int timer = 0, n;

void ts(int v) {
    used[v] = timer;
    for (auto u : g[v]) {
        if (used[u] != timer) {
            ts(u);
        }
    }
    t_s.push_back(v);
}

void dfs(int v) {
    color[v] = timer;
    for (auto u : t_g[v]) {
        // cout << "HDH " << u << ' ';
        if (!color[u]) {
            dfs(u);
        }
    }
}

void solve() {
    timer++;
    t_s.clear();
    for (int i = 0; i < n; i++) {
        if (used[i] != timer) {
            ts(i);
        }
    }
    reverse(t_s.begin(), t_s.end());
    // for (auto u : t_s) {
    //     cout << u << ' ';
    // }
    // cout << '\n';
    color.assign(n, 0);
    for (auto u : t_s) {
        if (!color[u]) {
            dfs(u);
            timer++;
        }
    }
}

signed main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    cout.precision(20);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int m, gg;
    cin >> n >> m >> gg;
    vector<pair<int, int>> edge;
    g.resize(n);
    t_g.resize(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        t_g[b].push_back(a);
        edge.push_back({a, b});
    }
    used.assign(n, -1);
    solve();
    vector<int> color1 = color;
    // for (auto u : color1) {
    //     cout << u << ' ';
    // }
    // cout << '\n';
    // exit(0);
    vector<int> sbmsk;
    for (int i = 1; i < (1 << m); i++) {
        g.assign(n, {});
        t_g.assign(n, {});
        for (int j = 0; j < m; j++) {
            if ((i >> j) & 1) {
                g[edge[j].second].push_back(edge[j].first);
                t_g[edge[j].first].push_back(edge[j].second);
            } else {
                t_g[edge[j].second].push_back(edge[j].first);
                g[edge[j].first].push_back(edge[j].second);
            }
        }
        solve();
        bool fl = true;
        for (int j = 0; j < m; j++) {
            for (int j1 = 0; j1 < m; j1++) {
                fl &= ((color1[j] == color1[j1] && color[j] == color[j1]) || (color1[j] != color1[j1] && color[j] != color[j1]));
            }
        }
        if (fl) {
            sbmsk.push_back(i);
        }
    }
    int mx = 0, cnt = 0;
    for (int j = 0; j < (1 << m); j++) {
        bool fl = false;
        for (auto u : sbmsk) {
            fl |= ((j | u) == j);
        }
        if (!fl) {
            if (__builtin_popcount(j) > mx) {
                mx = __builtin_popcount(j);
                cnt = 1;
            } else if (__builtin_popcount(j) == mx) {
                cnt++;
            }
        }
    }
    cout << mx << ' ' << cnt << '\n';
}