#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<bool>> g, all, h;
vector <int> used, used2;
int n, m, test;
int col = 0, mx = 0, ans = 1;
void dfs(int v) {
    all[v][v] = 1;
    used[v] = 1;
    for (int u = 0; u < n; u++) {
        if (g[v][u]) {
            if (!used[u]) dfs(u);
            for (int w = 0; w < n; w++) {
                if (all[u][w])
                    all[v][w] = 1;
            }
            if (used[u] == 2) {
                for (int w = 0; w < n; w++) {
                    if (used[w] == 2)
                        all[v][w] = 1;
                }
            }
        }
    }
    used[v] = 2;
}
bool dfs2(int v) {
    used2[v] = 1;
    bool flag = false;
    for (int u = 1; u < col; u++) {
        if (h[v][u]) {
            if (used2[u] == 1)
                return true;
            if (!used2[u])
                flag |= dfs2(u);
        }
    }
    used2[v] = 2;
    return flag;
}
void solve() {
    cin >> n >> m >> test;
    g = all = vector<vector<bool>> (n, vector<bool>(n, false));
    used = vector<int>(n, 0);
    for (int i = 0; i < m; i++) {
        int f, t;
        cin >> f >> t;
        f--; t--;
        g[f][t] = 1;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) dfs(i);
    }
    for (int v = 0; v < n; v++) {
        for (int u = 0; u < n; u++) {
            if (all[v][u]) {
                for (int w = 0; w < n; w++) {
                    if (all[u][w])
                        all[v][w] = 1;
                }
            }
        }
    }
    used = vector<int>(n, 0);
    for (int v = 0; v < n; v++) {
        if (!used[v]) {
            used[v] = ++col;
            for (int u = 0; u < n; u++) {
                if (all[v][u] && all[u][v] && v != u)
                    used[u] = col;
            }
        }
    }
    col++;
    vector <int> cnt(col, 0);
    for (int v = 0; v < n; v++) {
        cnt[used[v]]++;
    }
    h = vector<vector<bool>> (col, vector<bool>(col, false));
    for (int v = 0; v < n; v++) {
        for (int u = 0; u < n; u++) {
            if (used[v] != used[u] && g[v][u])
                h[used[v]][used[u]] = 1;
        }
    }
    for (int v = 1; v < col; v++) {
        for (int u = 1; u < col; u++) {
            if (h[v][u]) {
                h[v][u] = 0;
                h[u][v] = 1;
                used2 = vector<int>(col, 0);
                mx += dfs2(v);
                h[v][u] = 1;
                h[u][v] = 0;
            }
        }
    }
    for (int i = 0; i < col; i++) {
        mx += max(0ll, cnt[i] - 1);
        ans *= max(1ll, cnt[i]);
    }
    cout << mx << endl << ans << endl;
}
signed main() {
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}
