#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> gr;
vector<int> vst;
vector<int> tp;
int ans = 0;
void dfs(int v, int ok, int z) {
    vst[v] = 1;
    ans += ok;
    for (auto x : gr[v]) {
        if (!vst[x]) dfs(x, 1, z);
    }
    if (z) tp.push_back(v);
}
const int N = 2001;
int p[N];
int h[N];
int get(int v) {
    if (v == p[v]) return v;
    return p[v] = get(p[v]);
}
void unite(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    h[u] = max(h[u], h[v] + 1);
    p[v] = u;
}
int r[N][N];
signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int n, m, g; cin >> n >> m >> g;
    for (int i = 0; i < n; i++) {
        p[i] = i;
        h[i] = 1;
    }
    gr.resize(n); vst.resize(n);
    vector<int> deg(n);

    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >>v;
        u--; v--;
        gr[u].push_back(v);
        deg[v]++;
        r[u][v] = 1;
    }
    for (int i = 0; i < n; i++) {
        if (!vst[i]) dfs(i, 0, 1);
    }
    reverse(tp.begin(), tp.end());
    int cnt = 0;
    vector<set<int>> can(n);
    for (int i = 0; i < n; i++) {
        for (int j = i; j >= 0; j--) {
            if (!r[j][i]) continue;
            if (can[i].find(j) == can[i].end()) {
                cnt++;
            }
            can[i].insert(j);
            for (auto y : can[j]) {
                can[i].insert(y);
            }
        }
    }
    cout << m - cnt << '\n';
    cout << "1\n";
    return 0;
}
