#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <unordered_set>
#include <fstream>
#include <algorithm>
#include <unordered_map>
#include <queue>

using ll = long long;
#define endl '\n'
 #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unrool-loops")

using namespace std;

const int N = 3000 + 1, mod = 1e9 + 7;
int n, m, k, q;
int st = 1;
int G;
vector<vector<int>> g;

bool g2[N][N]{};
void solve() {
    cin >> n >> m >> G;
    g.resize(n);
    vector<int> in(n, 0), out(n, 0);
    for (int i =0; i < m; i++) {
        int v, u; cin >> v >> u; --v;--u;
        if (u != (v + 1) % n) {
            g[v].push_back(u);
            out[v]++; in[u]++;
        }
    }
    int ans = 1e9;
    
    for (int i = 0; i < n; i++) {
        int l = i, r = (i + 1) % n;
        while ((out[r] == 0)) {
            r = (r + 1) % n;
            if (l == r) {ans = 1; break;}
        }
        while (in[l] == 0) {
            l = (l + n - 1) % n;
            if (l == r) {ans = 1; break;}
        }
        g2[l][r] = true;
    }
    for (int len = n - 2; len > 0; len--) {
        for (int j = 0; j < n; j++) {
            if (g2[j][(j + len + 1) % n] || g2[(j + n - 1) % n][(j + len) % n]) g2[j][(j + len) % n] = true;
        }
    }
    for (int i = 0; i < n; i++) {
        vector<int> dp(n, 1e9);
        dp[i] = 0;
        queue<int> q;
        q.push(i);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (int u = 0; u < n; u++) {
                if (!g2[v][u]) continue;
                if (u == i) {
                    ans = min(ans, dp[v] + 1);
                } else if (dp[u] > dp[v] + 1) {
                    dp[u] = dp[v] + 1;
                    q.push(u);
                }
            }
        }
    }
    cout << 0 << ' ' << 1 << endl;
}


#define LOCAL
signed main() {
	ios_base::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif 
    solve();
}