#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

//#define int long long

using ll = long long;
using namespace std;

const int MAXN = 2000;

int c = 0;
vector<int> t, used1(MAXN), used2(MAXN);
vector<vector<int>> g(MAXN), gr(MAXN);

void dfs(int v, vector<int> &used) {
    used[v] = 1;
    for (auto u : g[v]) {
        if (!used[u]) {
            dfs(u, used);
        }
    }
    t.push_back(v);
}

void comp(int v, vector<int> &used) {
    used[v] = c;
    for (auto u : gr[v]) {
        if (!used[u]) {
            comp(u, used);
        }
    }
}

void solve() {
    int n, m, kal, ans = 0, cnt = 1;
    cin >> n >> m >> kal;
    vector<int> cur1(n + 1, 0), cur2(n + 1, -1);
    vector<pair<int, int>> e;
    for (int i = 0; i < m; i++) {
        int v, u;
        cin >> v >> u;
        v--;
        u--;
        e.emplace_back(v, u);
        g[v].push_back(u);
        gr[u].push_back(v);
    }
    for (int i = 0; i < n; i++) {
        if (!used1[i]) {
            dfs(i, used1);
        }
    }
    used1.assign(n, 0);
    reverse(t.begin(), t.end());
    for (int i = 0; i < n; i++) {
        if (!used1[t[i]]) {
            c++;
            comp(t[i], used1);
        }
    }
    for (int j = 0; j < m; j++) {
        swap(e[j].first, e[j].second);
        g.clear();
        gr.clear();
        g.resize(n);
        gr.resize(n);
        for (int i = 0; i < m; i++) {
            auto [v, u] = e[i];
            g[v].push_back(u);
            gr[u].push_back(v);
        }
        used2.assign(n, 0);
        t.clear();
        for (int i = 0; i < n; i++) {
            if (!used2[i]) {
                dfs(i, used2);
            }
        }
        c = 0;
        used2.assign(n, 0);
        reverse(t.begin(), t.end());
        for (int i = 0; i < n; i++) {
            if (!used2[t[i]]) {
                c++;
                comp(t[i], used2);
            }
        }
        bool flag = 0;
        cur1.assign(n + 1, 0);
        cur2.assign(n + 1, -1);
        for (int i = 0; i < m; i++) {
            if (cur2[used2[i]] != -1) {
                if (used1[i] != cur2[used2[i]]) {
                    flag = 1;
                    break;
                }
            } else {
                if (cur1[used1[i]] != 0) {
                    flag = 1;
                    break;
                }
                cur2[used2[i]] = used1[i];
                cur1[used1[i]] = 1;
            }
        }
        ans += flag;
        swap(e[j].first, e[j].second);
    }
    cout << ans << " " << cnt << "\n";
}

signed main() {
    int tests = 1;
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
//    cin >> t;
#else
    ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
#endif
//    cin >> t;
    while (tests--) {
        solve();
    }
}
