#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int mod = 1e9 + 7;

void solve3(int n, int m, vector<vector<int>> g) {
    cout << m - n + 1 << ' ' << 1 << '\n';
}

void dfs(int v, vector<vector<int>>& g, vector<int>& mn, vector<char>& used) {
    used[v] = true;
    for (int i : g[v]) {
        mn[i] = (mn[i] == -1 ? v : min(mn[i], v));
        if (used[i]) {
            continue;
        }
        dfs(i, g, mn, used);
    }
}

void dfs2(int v, vector<vector<int>>& g, vector<int>& mn, vector<char>& used, int& ans) {
    used[v] = true;
    for (int i : g[v]) {
        if (v != mn[i]) {
            ++ans;
        }
        if (used[i]) {
            continue;
        }
        dfs(i, g, mn, used);
    }
}

void solve4(int n, int m, vector<vector<int>> g) {
    vector<int> mn(n, -1);
    vector<char> used(n, false);
    int nx = 0, ans = 0;
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs(i, g, mn, used);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs2(i, g, mn, used, ans);
        }
    }
    cout << ans << ' ' << 1 << '\n';
}

void solve() {
    int n, m, g;
    cin >> n >> m >> g;
    vector<vector<int>> gr(n);
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        --u, --v;
        gr[u].push_back(v);
    }
    if (g == 3) {
        solve3(n, m, gr);
        return;
    }
    if (g == 4) {
        solve4(n, m, gr);
        return;
    }
    cout << "1 1\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}
