#include <bits/stdc++.h>

using ll = long long;
using namespace std;


class graph {
    int n, m, g;
    vector <vector <int>> gr;
    vector <vector <int>> rgr{};
    vector <int> vis, topsort;
    vector <vector <int>> comp;
    vector <int> tr;
    void dfs1(int num) {
        vis[num] = 1;
        for (int next : gr[num]) {
            if (!vis[next]) {
                dfs1(next);
            }
        }
        topsort.push_back(num);
    }
    void dfs2(int num, int col) {
        vis[num] = col;
        comp[col].push_back(num);
        for (int next : rgr[num]) {
            if (vis[next] == - 1) {
                dfs2(next, col);
            }
        }
    }
    void dfs3(int num, vector <vector <int>> &ngr, vector <int> &vis, int a = - 1, int b = - 1) {
        vis[num] = 1;
        for (int next : ngr[num]) {
            if (!vis[next] && !(num == a && next == b)) {
                dfs3(next, ngr, vis, a, b);
            }
        }
    }
    int get(vector <int> &ind) {
        int k = ind.size();
        vector <vector <int>> gr1(k), gr2(k);
        for (int i = 0; i < k; ++i) {
            for (int next : gr[i]) {
                if (vis[i] == vis[next]) {
                    gr1[tr[i]].push_back(tr[next]);
                }
            }
        }
        vector <int> vis(k, 0);
        for (int num = 0; num < k; ++num) {
            for (int next : gr1[num]) {
                fill(vis.begin(), vis.end(), 0);
                gr1[next].push_back(num);
                dfs3(num, gr1, vis, num, next);
//                cout << ind[num] << " " << ind[next] + 1 << '\n';
                int c = *min_element(vis.begin(), vis.end());
//                cout << c << '\n';
                if (c == 0) {
                    gr2[num].push_back(next);
                    gr2[next].push_back(num);
                }
                gr1[next].pop_back();
            }
        }
        int counter = 0;
        fill(vis.begin(), vis.end(), 0);
        for (int num = 0; num < k; ++num) {
            if (!vis[num]) {
                ++counter;
                dfs3(num, gr2, vis);
            }
        }
        return k - counter;
    }
public:
    void init() {
        cin >> n >> m >> g;
        gr.resize(n);
        rgr.resize(n);
        vis.resize(n);
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            --a;
            --b;
            gr[a].push_back(b);
            rgr[b].push_back(a);
        }
    }
    void get_comp() {
//        comp.push_back({});
//        for (int i = 0; i < n; ++i) {
//            comp[0].push_back(i);
//        }
//        fill(vis.begin(), vis.end(), 0);
        for (int i = 0; i < n; ++i) {
            if (!vis[i]) {
                dfs1(i);
            }
        }
        reverse(topsort.begin(), topsort.end());
        int col = 0;
        fill(vis.begin(), vis.end(), - 1);
        for (int num : topsort) {
            if (vis[num] == - 1) {
                comp.push_back({});
                dfs2(num, col);
                ++col;
            }
        }
    }
    void get_ans() {
        int ans = 0;
        tr.resize(n);
        for (int i = 0; i < comp.size(); ++i) {
            for (int j = 0; j < comp[i].size(); ++j) {
                tr[comp[i][j]] = j;
            }
        }
        for (int i = 0; i < comp.size(); ++i) {
            ans += get(comp[i]);
        }
        cout << ans << '\n' << 1 << '\n';
    }
};

void solve() {
    graph g;
    g.init();
    g.get_comp();
    g.get_ans();
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
}
