#include <bits/stdc++.h>

using ll = long long;

using namespace std;

#define int ll

int ans;

vector<vector<int>> g;
vector<int> cnt;
vector<int> used;

int dfs(int v) {
    int longest = 0;
    used[v] = 1;
    for (auto u : g[v]) {
        if (!used[u]) {
            longest = max(longest, dfs(u) + 1);
        }
    }
    return longest;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int n, m, gr;
    cin >> n >> m >> gr;
    assert(gr == 3 || gr == 4);
    ans = m;
    g.resize(n);
    cnt.assign(n, 0);
    used.assign(n, 0);
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        v--;
        u--;
        g[v].push_back(u);
        cnt[u]++;
    }
    for (int i = 0; i < n; i++) {
        if (cnt[i] == 0) {
            ans -= dfs(i);
        }
    }
    cout << ans << " " << 1;

    cout << "\n";
    return 0;
}