#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;

const ll inf = 1e18;
const ll mod = 1e9 + 7;

ll n, m, gg;
vector<vector<ll>> g1;
vector<vector<ll>> g2;
vector<vector<ll>> g;
vector<ll> was;
vector<ll> c;
vector<ll> res;
ll col = 0;

void dfs1(ll v) {
    was[v] = 1;
    for(ll to : g1[v]) {
        if (was[to] == 0) {
            col++;
            dfs1(to);
        }
    }
    res.push_back(v);
}

void dfs2(ll v, ll c1) {
    was[v] = 1;
    c[v] = c1;
    for(ll to : g2[v]) {
        if (was[to] == 0) {
            dfs2(to, c1);
        }
    }
}

void solve() {
    cin >> n >> m >> gg;
    g.assign(n, {});
    g1.assign(n, {});
    g2.assign(n, {});
    was.assign(n, 0);
    c.assign(n, 0);
    vector<pair<ll, ll>> z(m);
    for(int i = 0; i < m; i++) {
        ll a, b; cin >> a >> b;
        a--; b--;
        g1[a].push_back(b);
        g2[b].push_back(a);
        g[a].push_back(b);
        g[b].push_back(a);
        z[i] = {a, b};
    }
    for(int i = 0; i < n; i++) {
        if (was[i] == 0) {
            dfs1(i);
        }
    }
    reverse(res.begin(), res.end());
    fill(was.begin(), was.end(), 0);
    res.clear();
    ll c1 = 1;
    for(int i = 0; i < n; i++) {
        ll v = res[i];
        if (was[v] == 0) {
            dfs2(v, c1);
            c1++;
        }
    }
    vector<ll> c_need = c;
//    if (m <= 20) {
//        for(int i = 0; i < (1 << m); i++) {
//            g.assign(n, {});
//            g1.assign(n, {});
//            g2.assign(n, {});
//            was.assign(n, 0);
//            c.assign(n, 0);
//            for(int j = 0; j < m; j++) {
//                if ((i & (1 << j)) == 0) continue;
//                ll a = z[j].first, b = z[j].second;
//                g[a].push_back(b);
//                g1[b].push_back(a);
//                g[a].push_back(b);
//                g[b].push_back(a);
//            }
//            for(int i1 = 0; i1 < (1 << m); i1++) {
//                for(int j = 0; j < m; j++) {
//                    if ((i & (1 << j)) == 0) continue;
//                    ll a = z[j].first, b = z[j].second;
//                    g[a].push_back(b);
//                    g1[b].push_back(a);
//                    g[a].push_back(b);
//                    g[b].push_back(a);
//                }
//
//            }
//        }
//    }
    if (gg == 3) {
        cout << m - col << " " << 1 << "\n";
        return;
    }
    if (gg == 4) {
        cout << m - col << " " << 1 << "\n";
        return;
    }
}

int main() {
#ifdef KABANDJAN
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}
