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

using namespace std;
using namespace __gnu_pbds;

#define int long long
using ll = long long;

typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9 + 7;
const ll inf_ = 1e18 + 7;
const int mod = 1e9 + 7;

struct Hash {
    int mod2 = 1e9 + 7, p2 = 239;

    int sum(int a, int b) {
        a += b;
        if (a >= mod2) a -= mod2;
        return a;
    }

    int sub(int a, int b) {
        a -= b;
        if (a < 0) a += mod2;
        return a;
    }

    int mul(int a, int b) {
        return a * 1ll * b % mod2;
    }

    vector<int> h, pr;

    Hash(string s) {
        int n = s.size();
        h.resize(n);
        pr.resize(n + 1);
        h[0] = s[0];
        pr[0] = 1;
        for (int i = 1; i < n; i++)
            h[i] = sum(s[i], mul(h[i - 1], p2));
        for (int i = 1; i <= n; i++)
            pr[i] = mul(pr[i], p2);
    }

    int get(int l, int r) {
        return sub(h[r], (l ? mul(h[l - 1], pr[r - l + 1]) : 0));
    }
};

struct Fast {
    vector<vector<int>> g, gr, gc;
    vector<int> ts, col;
    vector<bool> used;

    void fts(int v) {
        used[v] = 1;
        for (auto u: g[v]) {
            if (used[u]) continue;
            fts(u);
        }
        ts.push_back(v);
    }

    vector<int> cnt;

    void paint(int v, int cl) {
        used[v] = 1;
        col[v] = cl;
        for (auto u: gr[v]) {
            if (used[u]) continue;
            paint(u, cl);
        }
    }

    void f(int v, int l, int r) {
        used[v] = 1;
        for (auto u: gc[v]) {
            if (v == l && u == r || used[u]) continue;
            f(u, l, r);
        }
    }

    int bp(int x, int n) {
        if (!n) return 1;
        if (n % 2) return x * bp(x, n - 1) % mod;
        int d = bp(x, n / 2);
        return d * d % mod;
    }

    void solve() {
        int n, m, _;
        cin >> n >> m >> _;
        if (n == m) {
            cout << n - 1 << '\n' << n;
            return;
        }
        g.resize(n);
        gr.resize(n);
        for (int i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            x--;
            y--;
            if (abs(x - y) == 1 || x == 0 && y == n - 1 || x == n - 1 && y == 0) continue;
            g[x].push_back(y);
            gr[y].push_back(x);
        }
        used.resize(n);
        for (int v = 0; v < n; v++) {
            if (!used[v])
                fts(v);
        }
        reverse(ts.begin(), ts.end());
        used.assign(n, 0);
        col.resize(n);
        int cl = 0;
        int ans = 0, kl = 1;
        for (auto v: ts) {
            if (!used[v]) {
                cnt.emplace_back();
                paint(v, cl), cl++;
            }
        }
        if (cl == n) {
            cout << m - (m - n + 1) << '\n' << n;
            return;
        }
        map<int, int> h;
        int d = 0;
        for (auto x: col) h[x]++;
        vector<bool> type(n);
        for (int v = 0; v < n; v++) {
            if (h[col[v]] > 1) type[v] = 1, d++;
        }
        cout << d << '\n' << 0;/*
        int last = -1;
        for(int i = 0; i < n;)*/
    }
};

signed main() {
    int __ = 1;
    //cin >> __;
    while (__--) {
        Fast().solve();
        cout << '\n';
    }
    return 0;
}
