#include <bits/stdc++.h>

using namespace std;

bool is_d(int i, int v, vector<vector<int>> &gr, vector<bool> &used, int st) {
    if (used[i]) return false;
    used[i] = true;
    if (i == v) return true;
    for (auto &j : gr[i]) {
        if (i == st && j == v) continue;
        if (is_d(j, v, gr, used, st)) return true;
    }
    return false;
}

int ansdag(vector<vector<int>> &gr) {
    int n = gr.size();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (auto &j : gr[i]) {
            vector<bool> used(n, false);
            if (is_d(i, j, gr, used, i)) {
                ans++;
            }
        }
    } 
    return ans;
}

void dfs(int i, vector<vector<int>> &gr, vector<bool> &used) {
    if (used[i]) return;
    used[i] = true;
    for (auto &j : gr[i]) dfs(j, gr, used);
}

int cnt_comps(vector<vector<int>> &gr) {
    int n = gr.size();
    vector<bool> used(n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i, gr, used);
            ans++;
        }
    }
    return ans;
}

int ans_comp(vector<vector<int>> &gr) {
    int n = gr.size();
    //vector<vector<int>> gr2(n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (auto &j : gr[i]) {
            vector<bool> used(n, false);
            if (!is_d(i, j, gr, used, i)) {
                ans++;
                gr[j].push_back(i);
            }
        }
    }
    return ans;
}

int ans(vector<vector<int>> &gr, int g) {
    int n = gr.size();
    vector<vector<bool>> d(n, vector<bool> (n, false));
    for (int i = 0; i < n; i++) {
        dfs(i, gr, d[i]);
    }
    vector<vector<int>> comps;
    vector<int> c(n, -1), comp_ind(n, -1);
    for (int i = 0; i < n; i++) {
        if (c[i] != -1) continue;
        int cur_comp = comps.size();
        comps.push_back(vector<int> (0));
        for (int j = 0; j < n; j++) {
            if (d[i][j] && d[j][i]) {
                comp_ind[j] = comps[cur_comp].size();
                c[j] = cur_comp;
                comps[cur_comp].push_back(j);
            }
        }
    }
    int ans = 0;
    vector<vector<int>> gr2(comps.size());
    for (int i = 0; i < n; i++) {
        for (auto &j : gr[i]) {
            assert(c[i] != -1);
            assert(c[j] != -1);
            assert(comp_ind[i] != -1);
            assert(comp_ind[j] != -1);
            if (c[i] != c[j]) {
                gr2[c[i]].push_back(c[j]);
            }
        }
    }
    ans += ansdag(gr2);
    for (int i = 0; i < n; i++) {
        assert(comps[c[i]][comp_ind[i]] == i);
    }
    for (int cmp = 0; cmp < comps.size(); cmp++) {
        vector<vector<int>> gr3(comps[cmp].size());
        for (auto &i : comps[cmp]) {
            for (auto &j : gr[i]) {
                if (c[j] != cmp) continue;
                gr3[comp_ind[i]].push_back(comp_ind[j]);
            }
        }
        ans += ans_comp(gr3);
    }
    if (g == 5 || g == 6) {
        assert(ans == ans_comp(gr));
    }
    return ans;
}

int main() {
    int n, m, g;
    cin >> n >> m >> g;
    vector<vector<int>> gr(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        gr[u].push_back(v);
    }
    int lans = ans(gr, g);
    cout << lans << " " << 1 << "\n";
    //cout << ansdag(gr) << " " << 1 << "\n";
}