#include<bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define int long long
vector<vector<int>> g;
vector<int> color;
int timer = 1;

void dfs(int v) {
    color[v] = timer;
    for (auto u : g[v]) {
        if (color[u] != color[v]) {
            dfs(u);
        }
    }
}


bool cmp(pair<int, int> a, pair<int, int>  b) {
    if (a.second - a.first != b.second - b.first) {
        return a.second - a.first < b.second - b.first;
    }
    return a.first < b.first;
}

signed main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    cout.precision(20);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, gg;
    cin >> n >> m >> gg;
    g.resize(n);
    color.resize(n);
    // for (int i = 0; i < n; i++) color[i] = i;
    vector<pair<int, int>> edge;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        edge.push_back({a - 1, b - 1});
        // g[a - 1].push_back(b - 1);
    }
    sort(edge.begin(), edge.end(), cmp);
    int ans = 0;
    for (auto [a, b] : edge) {
        timer++;
        dfs(a);
        if (color[b] == timer) {
            ans++;
        } else {
            g[a].push_back(b);
            dfs(a);
            // for (auto u : color) {
            //     cout << u << ' ';
            // }
            // cout << '\n';
        }
    }
    cout << n - 1 << '\n' << 1 << '\n';
}