#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

vector<set<int>> g;
vector<set<int>> rg;
vector<multiset<int>> cg;
int n, m, T;

mt19937 rnd(15281214);

int rand(int l, int r) {
    return l + rnd() % (r - l + 1);
}

void ts_dfs(int v, vector<int> &used, vector<int> &ts, vector<set<int>> &g) {
    used[v] = 1;
    for (auto u : g[v]) {
        if (!used[u]) {
            ts_dfs(u, used, ts, g);
        }
    }
    ts.push_back(v);
}

vector<int> tsort(vector<set<int>> &g) {
    vector<int> res; 
    vector<int> used(n + 1);
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            ts_dfs(i, used, res, g);
        }
    }
    reverse(res.begin(), res.end());
    return res;
}

vector<int> color;
int tc = 1;
int ud = 0, cnt = 1;

void f_kss(int v, vector<set<int>> &g) {
    color[v] = tc;
    for (auto u : g[v]) {
        if (!color[u]) {
            f_kss(u, g);
        }
    }
}

vector<int> nc;
int kk = 1;
void f_kss2(int v, vector<set<int>> &g) {
    nc[v] = kk;
    for (auto u : g[v]) {
        if (!nc[u]) {
            f_kss2(u, g);
        }
    }
}


bool flag = false;

void dfs(int v, vector<int> &used) {
    used[v] = 1;
    for (auto u : cg[v]) {
        if (used[u] == 0)
            dfs(u, used);
        if (used[u] == 1)
            flag = 1;
    }
    used[v] = 2;
}

bool cyc() {
    flag = 0;
    vector<int> used(n + 1);
    for (int i = 1; i <= n; i++) {
        if (!used[i])
        dfs(i, used);
    }
    return flag;
}

void solve() {
    cin >> n >> m >> T;
    g.resize(n + 1);
    rg.resize(n + 1);
    cg.resize(n + 1);
    color.resize(n + 1);
    nc.resize(n + 1);
    cnt = 1;
    vector<pair<int, int>> edges(m);
    for (int i = 0, a, b; i < m; i++) {
        cin >> a >> b;
        edges[i] = {a, b};
        g[a].emplace(b);
        rg[b].emplace(a);
    }
    auto ts = tsort(g);
    for (auto v : ts) {
        if (!color[v]) {
            f_kss(v, rg);
            tc++;
        }
    }
    vector<vector<int>> srtd(n + 1);
    for (int i = 1; i <= n; i++) {
        srtd[color[i]].push_back(i);
    }
    for (auto &v : srtd) {
        sort(v.begin(), v.end());
    }
    sort(srtd.begin(), srtd.end());

    for (int i = 0; i < m; i++) {
        auto [a, b] = edges[i];
        if (color[a] == color[b])
            continue;
        cg[color[a]].emplace(color[b]);
    }
    for (int i = 0; i < m; i++) {
        auto [a, b] = edges[i];
        if (color[a] == color[b]) {
            g[a].erase(b);
            g[b].insert(a);
            rg[b].erase(a);
            rg[a].insert(b);
            kk = 1;
            for (int j = 1; j <= n; j++)
                nc[j] = 0;
            auto ts2 = tsort(g);
            for (auto v : ts2) {
                if (!nc[v]) {
                    f_kss2(v, rg);
                    kk++;
                }
            }
            vector<vector<int>> srtd2(n + 1);
            for (int i = 1; i <= n; i++) {
                srtd2[nc[i]].push_back(i);
            }
            for (auto &v : srtd2) {
                sort(v.begin(), v.end());
            }
            sort(srtd2.begin(), srtd2.end());
            if (srtd != srtd2 && rand(1, 5) < 5) {
                ud++;
                cerr << a << " " << b << "\n";
            }
            else {
                g[a].insert(b);
                g[b].erase(a);
                rg[b].insert(a);
                rg[a].erase(b);
            }
        }
        else {
            int A = a, B = b;
            a = color[a];
            b = color[b];
            cg[a].erase(cg[a].find(b));
            cg[b].insert(a);
            if (cyc()) {
                ud++;
                cerr << A << " " << B << "\n";
            }
            cg[b].erase(cg[b].find(a));
            cg[a].insert(b);
        }
    }
    cout << ud << "\n" << cnt;
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    while (t--)
        solve();
}