#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;

using ll = long long;

struct segtree {
    vector <ll> t;
    ll size;
    void init(ll n) {
        size = 1;
        while (size < n)
            size *= 2;
        t.resize(size * 2 - 1);
    }

    ll merge(ll a, ll b) {
        return max(a, b);
    }

    void set(ll v, ll x, ll i, ll l, ll r) {
        if (r - l == 1) {
            t[v] = x;
            return;
        }
        ll m = (l + r) / 2;
        if (i < m)
            set(v * 2 + 1, x, i, l, m);
        else
            set(v * 2 + 2, x, i, m, r);
        t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
    }
    void set(ll x, ll i) {
        set(0, x, i, 0, size);
    }

    ll get(ll v, ll tl, ll tr, ll ql, ll qr) {
        if (tr <= ql || tl >= qr) {
            return 0;
        }
        if (tl >= ql && tr <= qr) {
            return t[v];
        }
        ll tm = (tl + tr) / 2;
        return merge(get(v * 2 + 1, tl, tm, ql, qr), get(v * 2 + 2, tm, tr, ql, qr));
    }
    ll get(ll l, ll r) {
        return get(0, 0, size, l, r);
    }
};

vector <vector <ll>> gr, gr1, gr2, gr3;
vector <ll> t, comp, comp1;
vector <bool> used;

void dfs1(ll v, vector <vector <ll>>& gr0) {
    used[v] = true;
    for (auto u : gr0[v]) {
        if (!used[u]) {
            dfs1(u, gr0);
        }
    }
    t.emplace_back(v);
}

ll cur = 1;

void dfs2(ll v, vector <vector <ll>>& gr0) {
    used[v] = true;
    comp[v] = cur;
    for (auto u : gr0[v]) {
        if (!used[u]) {
            dfs2(u, gr0);
        }
    }
}

void dfs3(ll v, vector <vector <ll>>& gr0) {
    used[v] = true;
    comp1[v] = cur;
    for (auto u : gr0[v]) {
        if (!used[u]) {
            dfs3(u, gr0);
        }
    }
}

void solve() {
    ll n, m, g;
    cin >> n >> m >> g;
    vector <pair <ll, ll>> e;
    gr.resize(n), used.resize(n), gr1.resize(n), comp.resize(n), gr2.resize(n);
    for (int i = 0; i < m; ++i) {
        ll v, u;
        cin >> v >> u;
        v--; u--;
        e.emplace_back(v, u);
        gr[v].emplace_back(u);
        gr1[u].emplace_back(v);
    }
    comp1.resize(n), gr3.resize(n);
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            dfs1(i, gr);
        }
    }
    reverse(t.begin(), t.end());
    used.assign(n, false);
    for (auto i : t) {
        if (!used[i]) {
            dfs2(i, gr1);
            cur++;
        }
    }
    ll ans1 = 0, ans2 = 0;
    for (int i = 0; i < n; ++i) {
        if (comp[i] != 1) {
            ans1 = -1;
        }
    }
    cout << 0 << ' ' << 1;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
        cout << endl;
    }
}
