#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;
vector<vector<int>> q;
vector<int> tops;
vector<bool> used;

void dfs(int v) {
    used[v] = true;
    for (auto u : g[v]) {
        if (!used[u]) dfs(u);
    }
    tops.push_back(v);
}

vector<int> cl;
void dfs(int v, int c) {
    cl[v] = c;
    for (auto u : q[v]) {
        if (cl[u] == -1) dfs(u, c);
    }
}

int m;

void print(int mask) {
    for (int i = 0; i < m; i++) {
        if ((mask >> i) & 1) cout << '1';
        else cout << '0';
    }
    cout << " ";
}

signed main() {
    int n, gg;
    cin >> n >> m >> gg;
    vector<pair<int, int>> pr(m);
    g.resize(n);
    q.resize(n);
    used.resize(n);
    cl.resize(n, -1);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        pr[i] = {x, y};
        g[x].push_back(y);
        q[y].push_back(x);
    }
    for (int i = 0; i < n; i++) if (!used[i]) dfs(i);
    reverse(tops.begin(), tops.end());
    int c = 0;
    for (auto i : tops) {
        if (cl[i] == -1) {
            dfs(i, c);
            c++;
        }
    }
    auto cl0 = cl;
    vector<bool> dp(1 << m);
    dp[0] = true;
    for (int mask = 1; mask < (1 << m); mask++) {
        g.clear();
        q.clear();
        tops.clear();
        used.clear();
        cl.clear();
        g.resize(n);
        q.resize(n);
        used.resize(n);
        cl.resize(n, -1);
        for (int i = 0; i < m; i++) {
            auto [x, y] = pr[i];
            if ((mask >> i) & 1) {
                g[y].push_back(x);
                q[x].push_back(y);
            } else {
                g[x].push_back(y);
                q[y].push_back(x);
            }
        }
        for (int i = 0; i < n; i++) if (!used[i]) dfs(i);
        reverse(tops.begin(), tops.end());
        c = 0;
        for (auto i : tops) {
            if (cl[i] == -1) {
                dfs(i, c);
                c++;
            }
        }
        vector<int> ma(n,  -1);
        bool f = true;
        for (int i = 0; i < n; i++) {
            if (ma[cl0[i]] == -1) ma[cl0[i]] = cl[i];
            else if (ma[cl0[i]] != cl[i]) f = false;
            if (ma[cl[i]] == -1) ma[cl[i]] = cl0[i];
            else if (ma[cl[i]] != cl0[i]) f = false;
        }
        dp[mask] = f;
    }
    int ans = 0, cans = 0;
    for (int mask = 0; mask < (1 << m); mask++) {
        bool res = true;
        for (int mask2 = mask; mask2 != 0; mask2 = (mask & (mask2 - 1))) {
            if (dp[mask2]) res = false;
        }
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if ((mask >> i) & 1) cnt++;
        }
        if (res) {
            if (cnt > ans) {
                ans = cnt;
                cans = 1;
            } else if (cnt == ans) {
                cans++;
            }
        }
    }
    cout << ans << '\n' << cans;
}
