#include <bits/stdc++.h>

using ll = long long;
using namespace std;

void dfs(ll num, vector <vector <ll>> &gr, vector <ll> &topsort, vector <ll> &vis) {
    vis[num] = 1;
    for (ll next : gr[num]) {
        if (!vis[next]) {
            dfs(next, gr, topsort, vis);
        }
    }
    topsort.push_back(num);
}
const ll len = 2000;
void dfs1(ll num, vector <vector <ll>> &gr, vector <ll> &vis, ll &ans, vector <bitset <len>> &now) {
    vis[num] = 1;
    now[num][num] = 1;
    vector <ll> list{};
    for (ll next : gr[num]) {
        if (!vis[next]) {
            dfs1(next, gr, vis, ans, now);
            now[num] |= now[next];
        } else {
            list.push_back(next);
        }
    }
    for (ll next : list) {
        if (now[num][next]) {
            ++ans;
        }
    }
}
vector <int> get(vector <int> &c) {
    vector <int> nc;
    sort(c.begin(), c.end());
    for (auto v : c) {
        if (!nc.empty() && nc.back() == v - 1) {
            nc.pop_back();
        } else {
            nc.push_back(v);
        }
    }
    return nc;
}
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) {
        vis[num] = 1;
        for (int next : ngr[num]) {
            if (!vis[next]) {
                dfs3(next, ngr, vis);
            }
        }
    }
    int get(vector <int> &ind) {
        vector <vector <int>> ngr(ind.size());
        vector <vector <int>> rngr = ngr;
        for (int num : ind) {
            for (int next : gr[num]) {
                if (vis[num] == vis[next]) {
                    ngr[tr[num]].push_back(tr[next]);
                    rngr[tr[next]].push_back(tr[num]);
                }
            }
        }
        int k = ind.size();
        vector <int> vis(k, 0);
//        for (int i = 0; i < k; ++i) {
//            cout << i + 1 << ": ";
//            for (int next : ngr[i]) {
//                cout << next + 1 << ' ';
//            }
//            cout << endl;
//        }
        vector <vector <int>> resgr(k);
        for (int num = 0; num < k; ++num) {
            int l = ngr[num].size() - 1;
            for (int j = ngr[num].size() - 1; j >= 0; --j) {
                fill(vis.begin(), vis.end(), 0);
                swap(ngr[num][j], ngr[num][l]);
                swap(rngr[num][j], rngr[num][l]);
                int a = num, b = ngr[num][l];
//                cout << a + 1 << " " << b + 1 << endl;
//                cout << ind[a] + 1 << " " << ind[b] + 1 << '\n';
                rngr[b].pop_back();
                ngr[a].pop_back();
                ngr[b].push_back(a);
                rngr[a].push_back(b);
//                find
                dfs3(num, ngr, vis);
                int c = *min_element(vis.begin(), vis.end());
                fill(vis.begin(), vis.end(), 0);
                dfs3(num, rngr, vis);
                int d = *min_element(vis.begin(), vis.end());
//                cout << c << " " << d << "\n\n";
                if (!(c == 1 && d == 1)) {
                    resgr[a].push_back(b);
                    resgr[b].push_back(a);
                }
                ngr[b].pop_back();
                rngr[a].pop_back();
                rngr[b].push_back(a);
                ngr[a].push_back(b);
            }
        }
        fill(vis.begin(), vis.end(), 0);
        int counter = 0;
        for (int num = 0; num < k; ++num) {
            if (!vis[num]) {
                ++counter;
                dfs3(num, resgr, 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);
        }
//        cout << "GOOD" << endl;
    }
    void get_comp() {
        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;
            }
        }
//        for (int i = 0; i < n; ++i) {
//            cout << vis[i] << ' ';
//        }
//        cout << endl;
    }
    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 < n; ++i) {
//            cout << tr[i] << ' ';
//        }
//        cout << endl;
        for (int i = 0; i < comp.size(); ++i) {
            ans += get(comp[i]);
        }
//        vector <vector <int>> ngr(comp.size());
//        for (int num = 0; num < n; ++num) {
//            for (int next : gr[num]) {
//                if (vis[num] != vis[next]) {
//                    ngr[vis[num]].push_back(vis[next]);
//                }
//            }
//        }
//        ans += get1(ngr);
        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();
}
