#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using li = __int128;
using db = double;
using ld = long double;
using pi = pair <int, int>;
using pll = pair <ll, ll>;
#define all(x) x.begin(), x.end()

mt19937 rnd(time(NULL));

struct V {
    db x;
    db y;
};

V operator+ (const V& a, const V& b) {
    return {a.x + b.x, a.y + b.y};
}
db operator* (const V& a, const V& b) {
    return a.x * b.x + a.y * b.y;
}
db operator^ (const V& a, const V& b) {
    return a.x * b.y - a.y * b.x;
}
V operator* (const V& a, db k) {
    return {a.x * k, a.y * k};
}

ll bin_pow(ll a, ll s, ll mod) {
    ll res = 1;
    while (s) {
        if (s & 1) {
            res *= a;
            res %= mod;
        }
        a = (a * a) % mod;
        s >>= 1;
    }
    return res;
}


void solve() {
    int n, m, group;
    cin >> n >> m >> group;
    vector <vector <int>> g(n + 1);
    vector <pi> r(m);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        r[i] = {a, b};
    }
    for (int i = 1; i <= n; ++i) {
        sort(all(g[i]));
        g[i].push_back(n + 1);
    }
    int ans = m;
    vector <int> ts;
    vector <int> used(n + 2);
    used[n + 1] = 1;
    auto dfs = [&](auto self, int v)->void {
        used[v] = 1;
        for (auto u : g[v]) {
            if (!used[u]) self(self, u);
        }
        ts.push_back(v);
    };
    for (int i = 1; i <= n; ++i) if (!used[i]) dfs(dfs, i);
    reverse(all(ts));

    vector <int> color(n + 2);
    color[n + 1] = 1;
    int c = 1;
    auto dfs2 = [&](auto self, int v)->void {
        color[v] = c;
        for (auto u : g[v]) if (!color[u]) self(self, u);
    };

    for (int i = 0; i < n; ++i) {
        if (!color[ts[i]]) dfs2(dfs2, ts[i]), ++c;
    }
    vector <vector <int>> tss(c);
    for (auto i : ts) {
        tss[color[i]].push_back(i);
    }
    vector <int> ind(n + 1);
    for (auto el : tss) {
        for (int i = 0; i < el.size(); ++i) ind[el[i]] = i;
        int cnt = 0;
        for (int i = 0; i + 1 < el.size(); ++i) {
            int next = *lower_bound(all(g[el[i]]), el[i + 1]);
            if (next != el[i + 1]) ++cnt;
        }
        ans -= cnt - 1;
    }
    for (auto [a, b] : r) if (ind[b] - ind[a] == 1) --ans;
    cout << ans << '\n' << 1 << '\n';
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) solve();
    return 0;
}
