#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], t[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 : t[v]) {
        if (used[u]) continue;
        color(u);
    }
}

void 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++;
    }
}

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[u]) 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);
        t[y].insert(x);
    }
    int ans = 0;
    geth();
    int basedcmp = clr;
    vector<int> potential;
    for (int j = 0; j < m; j++) {
        auto [x, y] = edges[j];
        g[x].erase(y);
        g[y].insert(x);
        t[y].erase(x);
        t[x].insert(y);
        geth();
        if (clr != basedcmp) {
            potential.push_back(j);
        }
        g[y].erase(x);
        g[x].insert(y);
        t[y].insert(x);
        t[x].erase(y);
    }
    for (auto i : potential) {
        auto [x, y] = edges[i];
        g[x].erase(y);
        t[y].erase(x);
    }
    geth();
    for (auto i : potential) {
        auto [x, y] = edges[i];
        //assert(cmps[x] != cmps[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 << clr - cmpsv << ' ' << 5252 << '\n';
}

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