
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxn = 2000 + 10;
const int mod = 1e9 + 7;
vector<vector<int>> edges(maxn, vector<int>());
vector<bool> used(maxn, false);
int n, m, g;

void clean_used() {
    for (int i = 0; i <= n; i++) {
        used[i] = false;
    }
}

void dfs(int v, int a, int b) {
    used[v] = true;
    for (auto u : edges[v]) {
        if (!used[u]) {
            if (v != a || u != b) {
                dfs(u, a, b);
            }
        }
    }
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(15);
    cin >> n >> m >> g;
    int cou = 0;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        edges[a].push_back(b);
    }
    for (int i = 1; i <= n; i++) {
        for (auto j : edges[i]) {
            if (i + 1 == j || (i == n && j == 1)) {
                dfs(i, i, j);
                if (!used[j]) {
                    cou++;
                }
                clean_used();
            }
        }
    }
    if (cou == n) {
        cout << cou - 1 << " " << n << endl;
    } else {
        cout << cou << endl << 1 << endl;
    }

}
