#pragma GCC optimize("Ofast,inline")

#include <bits/stdc++.h>

using namespace std;

//#define int int64_t
#define fi first
#define se second
mt19937 gen(time(0));

const int N = 2e3 + 12;
vector <int> g[N];

bool used[N];
bool check(int v, int u) {
    fill(used, used + N, 0);
    used[v] = 1;
    queue <int> q;
    q.push(v);
    while(q.size() && !used[u]) {
        int v = q.front();
        q.pop();
        for(auto to : g[v]) {
            if(!used[to]) {
                used[to] = 1;
                q.push(to);
            }
        }
    }
    return used[u];
}

int32_t main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, G2;
    cin >> n >> m >> G2;
    vector <pair<int,int>> e;
    for(int i = 0; i < m; ++i) {
        int v, u;
        cin >> v >> u;
        e.push_back({v, u});
    }
    sort(e.begin(), e.end(), [&](pair <int,int> x, pair <int,int> y) {
        if(x.se - x.fi == y.se - y.fi)
            return x.fi < y.fi;
        return x.se - x.fi < y.se - y.fi;
    });
    int ans = 0;
    for(auto [v, u] : e) {
        if(check(u, v))
            continue;
        ans++;
        g[u].push_back(v);
    }
    cout << 0 << ' ' << 1;
    return 0;
}
