#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef string str;
mt19937 rnd(157);

#define all(a) a.begin(), a.end()
#define int long long


vector<vector<int>> g;
vector<vector<int>> gr;

vector<int> topsort;
vector<int> used;
vector<int> col;


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

void cdfs(int v) {
    for(int u : gr[v]) {
        if(col[u] == 0) {
            col[u] = col[v];
            cdfs(u);
        }
    }
}

vector<int> topsort2;
vector<int> used2;
vector<int> col2;

pair<int, int> rev1;

void dfs2(int v) {
    used2[v] = 1;
    for(int u : g[v]) {
        if(!used2[u] && make_pair(v, u) != rev1) {
            dfs2(u);
        }
    }
    if(v == rev1.second) {
        if(!used2[rev1.first]) {
            dfs2(rev1.first);
        }
    }
    topsort2.push_back(v);
}

void cdfs2(int v) {
    for(int u : gr[v]) {
        if(col2[u] == 0 && make_pair(u, v) != rev1) {
            col2[u] = col2[v];
            cdfs2(u);
        }
    }
    if(v == rev1.first) {
        if(col2[rev1.second] == 0) {
            col2[rev1.second] = col2[v];
            cdfs2(rev1.second);
        }
    }
}

vector<int> used3;

bool dfs3(int v) {
    used3[v] = 1;
    for(int u : g[v]) {
        if(!used3[u]) {
            dfs3(v);
        }
    }
}



signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int n, m, ah;
    cin >> n >> m >> ah;

    g.resize(n);
    gr.resize(n);

    vector<pair<int, int>> edges;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        gr[v].push_back(u);
        edges.emplace_back(u, v);
    }

    used.resize(n, 0);
    for(int i = 0; i < n; i++) {
        if(!used[i]) {
            dfs(i);
        }
    }
    reverse(all(topsort));
    col.resize(n, 0);
    int c = 1;
    for(int i = 0; i < n; i++) {
        if(col[topsort[i]] == 0) {
            col[topsort[i]] = c++;
            cdfs(topsort[i]);
        }
    }
    int ans1 = 0;
    for(int _ = 0; _ < m; _++) {
        rev1 = edges[_];
        auto[u, v] = rev1;
        used3.assign(n, 0);
        dfs3(u);
        if(!used3[v]) {
            ans1++;
        }
//        used2.assign(n, 0);
//        col2.assign(n, 0);
//        topsort2.clear();
//
//        for(int i = 0; i < n; i++) {
//            if(!used2[i]) {
//                dfs2(i);
//            }
//        }
//        reverse(all(topsort2));
//
//        c = 1;
//        for(int i = 0; i < n; i++) {
//            if(col2[topsort2[i]] == 0) {
//                col2[topsort2[i]] = c++;
//                cdfs2(topsort2[i]);
//            }
//        }
//        bool flag = false;
//        for(int i = 0; i < n; i++) {
//            if(col[i] != col2[i]) {
//                flag = true;
//            }
//        }
//        if(flag) {
//            ans1++;
//        }
    }
    if(ans1 == n) {
        cout << n << endl << n << endl;
    } else {
        cout << ans1 << endl << 1 << endl;
    }
}
