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

using namespace std;


struct e{
    int finish;
    int ind;
};

const int maxn = 21;
const int mod = 1e9 + 7;
vector<vector<e>> edges(maxn, vector<e>());
vector<vector<e>> back_edges(maxn, vector<e>());
vector<bool> used(maxn, false);
vector<int> order;
vector<int> all_comp;
int n, m, g;

void dfs1(int v, int mask) {
    used[v] = true;
    for (auto pai : back_edges[v]) {
        int u = pai.finish;
        int ind = pai.ind;
        if (!((mask >> ind) & 1)) {
            if (!used[u]) {
                dfs1(u, mask);
            }
        }
    }
    for (auto pai : edges[v]) {
        int u = pai.finish;
        int ind = pai.ind;
        if (((mask >> ind) & 1)) {
            if (!used[u]) {
                dfs1(u, mask);
            }
        }
    }
    order.push_back(v);
}

void dfs2(int v, int num, int mask) {
    all_comp[v] = num;
    for (auto pai : edges[v]) {
        int u = pai.finish;
        int ind = pai.ind;
        if (!((mask >> ind) & 1)) {
            if (all_comp[u] == -1) {
                dfs2(u, num, mask);
            }
        }
    }
    for (auto pai : back_edges[v]) {
        int u = pai.finish;
        int ind = pai.ind;
        if (((mask >> ind) & 1)) {
            if (all_comp[u] == -1) {
                dfs2(u, num, mask);
            }
        }
    }
}



vector<int> make_comp(int mask) {
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            dfs1(i, mask);
        }
    }
    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, mask);
            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;
    for (int i = 1; i <= n; i++) {
        used[i] = false;
    }
    return ans;
}

int cou_ones(int num) {
    int ans = 0;
    for (int i = 0; i <= 20; 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, i});
        back_edges[b].push_back({a, i});
    }
    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++) {
        bool check = true;
        for (int j = 0; j < m; j++) {
            if ((mask >> j) & 1) {
                if (!good_or_bad_mask[mask - (1 << j)]) {
                    check = false;
                }
            }
        }
        if (!check) {
            good_or_bad_mask[mask] = false;
        } else 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;
}
