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

using namespace std;

const int maxn = 2000 + 10;
const int mod = 1e9 + 7;
vector<vector<int>> edges(maxn, vector<int>());
vector<pair<int, int>> lst_edges;
vector<vector<int>> norm_edges(maxn, vector<int>());
vector<vector<int>> back_edges(maxn, vector<int>());
vector<bool> used(maxn, false);
vector<int> order;
vector<int> all_comp;
int n, m, g;

void dfs1(int v) {
    used[v] = true;
    for (auto u : back_edges[v]) {
        if (!used[u]) {
            dfs1(u);
        }
    }
    order.push_back(v);
}

void dfs2(int v, int num) {
    all_comp[v] = num;
    for (auto u : norm_edges[v]) {
        if (all_comp[u] == -1) {
            dfs2(u, num);
        }
    }
}



vector<int> make_comp(int mask) {
    for (int i = 0; i < m; i++) {
        if ((mask >> i) & 1) {
            norm_edges[lst_edges[i].second].push_back(lst_edges[i].first);
            back_edges[lst_edges[i].first].push_back(lst_edges[i].second);
        } else {
            norm_edges[lst_edges[i].first].push_back(lst_edges[i].second);
            back_edges[lst_edges[i].second].push_back(lst_edges[i].first);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            dfs1(i);
        }
    }
    reverse(order.begin(), order.end());
    all_comp = vector<int>(n + 1, -1);
    int num = 0;
    for (auto v : order) {
        if (all_comp[v] == -1) {
            dfs2(v, num);
            num++;
        }
    }
    vector<int> when_first_time(num, -1);
    int cool_num = 0;
    for (int i = 1; i <= n; i++) {
        if (when_first_time[all_comp[i]] == -1) {
            when_first_time[all_comp[i]] = cool_num;
            cool_num++;
        }
    }
    for (int i = 1; i <= n; i++) {
        all_comp[i] = when_first_time[all_comp[i]];
    }
    vector<int> ans = all_comp;
    all_comp.clear();
    for (int i = 1; i <= n; i++) {
        used[i] = false;
        norm_edges[i].clear();
        back_edges[i].clear();
    }
    return ans;
}

int cou_ones(int num) {
    int ans = 0;
    for (int i = 0; i < 30; i++) {
        if ((num >> i) & 1) {
            ans++;
        }
    }
    return ans;
}




signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(15);
    cin >> n >> m >> g;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
        lst_edges.push_back({a, b});
    }
    vector<int> q = make_comp(0);
    vector<bool> good_or_bad_mask((1 << m), true);
    vector<int> bad_mask;
    for (int mask = 1; mask < (1 << m); mask++) {
        if (make_comp(mask) == q) {
            good_or_bad_mask[mask] = false;
        }
    }
    vector<bool> could_use((1 << m), true);
    for (int i = 1; i < (1 << m); i++) {
        if (!good_or_bad_mask[i]) {
            could_use[i] = false;
        } else {
            for (int j = 0; j < m; j++) {
                if ((i >> j) & 1) {
                    if (!could_use[i - (1 << j)]) {
                        could_use[i] = false;
                        break;
                    }
                }
            }
        }
    }
    int siz = 0;
    int cou = 0;
    for (int i = 0; i < (1 << m); i++) {
        if (could_use[i]) {
            int new_siz = cou_ones(i);
            if (new_siz > siz) {
                siz = new_siz;
                cou = 1;
            } else if (new_siz == siz) {
                cou++;
            }
        }
    }
    cout << siz << endl << cou << endl;
}
