#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g, gr;
vector<int> used, ord;
vector<pair<int, int>> rebra;
int wwe = 0;

void dfs(int v, vector<unordered_set<int>>& ban) {
    used[v] = 1;
    for (auto to : g[v]) {
        if (ban[v].find(to) != ban[v].end()) continue;
        if (used[to]) continue;
        dfs(to, ban);
    }
    ord.push_back(v);
}

void paint(int v, vector<unordered_set<int>>& ban) {
    used[v] = 1;
    for (auto to : gr[v]) {
        if (ban[v].find(to) != ban[v].end()) continue;
        if (used[to]) continue;
        paint(to, ban);
    }
}

int KSS(int n, vector<unordered_set<int>>& ban) {
    used.clear(), used.resize(n);
    ord.clear();
    for (int i = 0; i < n; i++) {
        if (!used[i]) dfs(i, ban);
    }
    reverse(ord.begin(), ord.end());
    int c = 0;
    used.clear(), used.resize(n);
    for (auto i : ord) {
        if (!used[i]) {
            paint(i, ban);
            c++;
        }
    }
    return c;
}

vector<int> cur;
int C, ans = 0, col = 0;

void gen(int k, int n) {
    if (k == 0) {
        vector<unordered_set<int>> ban(n);
        int ind = 0, cnt = 0;
        for (auto i : cur) {
            if (i) {
                ban[rebra[ind].first].insert(rebra[ind].second);
            }
            ind++;
            cnt += i;
        }
        if (cnt == (C - KSS(n, ban))) {
            if (ans < cnt) {
                ans = cnt;
                col = 0;
            }
            if (ans == cnt) {
                col++;
            }
        }
    }
}

void solve() {
    int n, m; cin >> n >> m;
    int t; cin >> t;
    g.resize(n);
    gr.resize(n);
    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);
        rebra.emplace_back(u, v);
    }
    cout << n - 1 << '\n' << 0 << '\n';
    vector<unordered_set<int>> s(n);
    //C = KSS(n, s);
    //gen(m, n);

}

int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    solve();
}
