#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e3 + 1;

int n, m, g52;
unordered_set<int> g[maxn];
bool used[maxn];
vector<int> order;

const int MOD = 1e9 + 7;

int pw(int x, int n) {
    if (n == 0) return 1;
    int res = pw(x, n / 2);
    res = res * res % MOD;
    if (n & 1) res = res * x % MOD;
    return res;
}

void topsort(int v) {
    used[v] = 1;
    for (auto u : g[v]) {
        if (used[u]) continue;
        topsort(u);
    }
    order.push_back(v);
}

int clr = 0, cmp[maxn];

void color(int v) {
    used[v] = 1;
    cmp[v] = clr;
    for (auto u : g[v]) {
        if (used[u]) continue;
        color(u);
    }
}

vector<int> geth() {
    fill(used, used + n, 0);
    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        topsort(i);
    }
    reverse(order.begin(), order.end());
    fill(used, used + n, 0);
    fill(cmp, cmp + n, 0);
    clr = 0;
    for (auto u : order) {
        if (used[u]) continue;
        color(u);
        clr++;
    }
    map<int, int> mp1;
    for (int i = 0; i < n; i++) {
        mp1[cmp[i]] = i;
    }
    vector<int> ans1(n);
    for (int i = 0; i < n; i++) {
        ans1[i] = mp1[cmp[i]];
    }
    return ans1;
}

pair<int, int> edges[maxn];

vector<int> g1[maxn];

int cmpsv = 0;

void recalc(int v) {
    used[v] = 1;
    for (auto u : g1[v]) {
        if (used[v]) continue;
        recalc(u);
    }
}

void solve() {
    cin >> n >> m >> g52;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y; x--, y--;
        edges[i] = {x, y};
        g[x].insert(y);
    }
    int ans = 0;
    vector<int> checkequal = geth();
    vector<int> potential;
    for (int i = 0; i < m; i++) {
        auto [x, y] = edges[i];
        g[x].erase(y);
        g[y].insert(x);
        vector<int> eq1 = geth();
        bool fl = 1;
        for (int i = 0; i < n; i++) {
            if (eq1[i] != checkequal[i]) {
                fl = 0;
            }
        }
        if (fl) {
            potential.push_back(i);
        }
        g[y].erase(x);
        g[x].insert(y);
    }
    for (auto i : potential) {
        auto [x, y] = edges[i];
        g[x].erase(y);
    }
    vector<int> cmps = geth();
    for (auto i : potential) {
        auto [x, y] = edges[i];
        assert(cmp[x] != cmp[y]);
        g1[cmp[x]].push_back(cmp[y]);
        g1[cmp[y]].push_back(cmp[x]);
    }
    fill(used, used + n, 0);
    for (int i = 0; i < clr; i++) {
        if (used[i]) continue;
        recalc(i);
        cmpsv++;
    }
    cout << cmpsv << ' ' << 52 << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tests = 1;
    while (tests--) solve();
}
