//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>

using namespace std;

/*

struct Update {
    long long add = 0;
    Update() : add(0) {}
    Update(long long add) : add(add) {}
    Update apply(Update other) {
        return add + other.add;
    }
};

struct Node {
    long long summ = 0, l = 0, r = 0;
    Node() : summ(0), l(0), r(0) {}
    Node(long long x) : summ(x) {}
    Node(long long x, long long l, long long r) : summ(x), l(l), r(r) {}
    Node merge(Node other) {
        return Node(summ + other.summ, l, other.r);
    }
    Node apply(Update other) {
        return Node(summ + other.add * (r - l), l, r);
    }
};

struct seg_tree {
    long long n;
    vector<long long> a;
    vector<Node> tree;
    vector<Update> updates;

    seg_tree(vector<long long> a2) {
        n = a2.size();
        a = a2;
        tree.resize(4 * n);
        updates.resize(4 * n);
        build(0, 0, n);
    }

    void push(long long v) {
        if (updates[v].add != 0) {
            updates[2 * v + 1] = updates[2 * v + 1].apply(updates[v]);
            updates[2 * v + 2] = updates[2 * v + 2].apply(updates[v]);
            tree[2 * v + 1] = tree[2 * v + 1].apply(updates[v]);
            tree[2 * v + 2] = tree[2 * v + 2].apply(updates[v]);
            updates[v] = 0;
        }
    }

    void build(long long v, long long l, long long r) {
        tree[v].l = l;
        tree[v].r = r;
        if (l == r - 1) {
            tree[v].summ = a[l];
            return;
        }
        long long mid = (l + r) / 2;
        build(2 * v + 1, l, mid);
        build(2 * v + 2, mid, r);
        tree[v] = tree[2 * v + 1].merge(tree[2 * v + 2]);
    }

    Node get(long long v, long long l, long long r, long long ql, long long qr) {
        //cout << v << endl;
        if (ql <= l && r <= qr) {
            //cout << "! " << v << endl;
            return tree[v];
        }
        if (qr <= l || r <= ql) {
            //cout << "? " << v << endl;
            return Node();
        }
        //cout << v << endl;
        push(v);
        //cout << v << endl;
        long long mid = (l + r) / 2;
        return get(2 * v + 1, l, mid, ql, qr).merge(get(2 * v + 2, mid, r, ql, qr));
    }


    Node get_q(long long l, long long r) {
        return get(0, 0, n, l, r);
    }


    void update(long long v, long long l, long long r, long long ql, long long qr, Update add) {
        //cout << "! " << v << " " << add.add << endl;
        if (ql <= l && r <= qr) {
            //cout << v << " " << add.add << endl;
            //cout << tree[v].summ << endl;
            tree[v] = tree[v].apply(add);
            //cout << tree[v].summ << " " << tree[v].r - tree[v].l << " " << add.add << endl;
            updates[v] = updates[v].apply(add);
            return;
        }
        if (qr <= l || r <= ql) {
            return;
        }
        push(v);
        long long mid = (l + r) / 2;
        update(2 * v + 1, l, mid, ql, qr, add);
        update(2 * v + 2, mid, r, ql, qr, add);
        tree[v] = tree[2 * v + 1].merge(tree[2 * v + 2]);
    }

    void update_q(long long l, long long r, long long add) {
        //cout << "! " << add << endl;
        update(0, 0, n, l, r, add);
    }
};

struct pt {
    long long x, y;
    pt() : x(0), y(0) {}
    pt(long long x, long long y) : x(x), y(y) {}
    pt(pt s, pt t) : x(t.x - s.x), y(t.y - s.y) {}

    long long operator*(pt other) {
        return x * other.y + y * other.x;
    }
    long long operator%(pt other) {
        return x * other.y - y * other.x;
    }

    pt operator*(long long k) {
        return pt(x * k, y * k);
    }

    pt operator+(pt other) {
        return pt(x + other.x, y + other.y);
    }

    pt operator-(pt other) {
        return pt(x - other.x, y - other.y);
    }
};

struct line {
    long long a, b, c;
    line() : a(0), b(0), c(0) {}
    line(pt s, pt t) {
        a = t.y - s.y;
        b = s.x - t.x;
        c = -(t.y * s.x - t.x * s.y);
        //(t.y - s.y) * t.x + (s.x - t.x) * t.y = -s.y * t.x + s.x * t.y
        //(t.y - s.y) * s.x + (s.x - t.x) * s.y = t.y * s.x - t.x * s.y
    }

    bool is_on_line(pt other) {
        return other.x * a + other.y * b + c == 0;
    }
};
*/

struct query {
    long long a, b, type;
    query() : a(0), b(0), type(0) {}
    query(long long a, long long b, long long type) : a(a), b(b), type(type) {}
    bool operator<(const query &other) {
        return make_pair(make_pair(a, b), type) < make_pair(make_pair(other.a, other.b), other.type);
    }
};

vector<vector<long long>> g, grev, comp;
vector<bool> used;
vector<long long> order;

void topsort(long long v) {
    used[v] = true;
    for (auto &i : g[v]) {
        if (!used[i]) {
            topsort(i);
        }
    }
    order.push_back(v);
}

void find_comp(long long v) {
    comp.back().push_back(v);
    used[v] = true;
    for (auto &i : grev[v]) {
        if (!used[i]) {
            find_comp(i);
        }
    }
}
vector<pair<long long, long long>> edges;

bool is_same(long long mask) {

}



signed main() {
    //ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    long long n, m, t;
    cin >> n >> m >> t;
    g.resize(n);
    grev.resize(n);
    edges.resize(m);
    vector<long long> not_them;
    for (auto &i : edges) {
        cin >> i.first >> i.second;
        i.first--;
        i.second--;
        if ((i.first + 1) % n != i.second) {
            //not_them.push_back(i.first);
            not_them.push_back(i.first);
        }
        g[i.first].push_back(i.second);
        grev[i.second].push_back(i.first);
    }
    /*
    vector<vector<long long>> start;
    used.assign(n, false);
    order.clear();
    for (long long i = 0; i < n; i++) {
        if (!used[i]) {
            topsort(i);
        }
    }
    reverse(order.begin(), order.end());
//    for (auto &i : order) {
//        cout << i << " ";
//    }
//    cout << endl;
    used.assign(n, false);
    for (auto &i : order) {
        if (!used[i]) {
            comp.push_back({});
            find_comp(i);
        }
    }
    sort(comp.begin(), comp.end());
//    for (auto &i : comp) {
//        for (auto &j : i)  {
//            cout << j << " ";
//        }
//        cout << endl;
//    }
//    cout << endl;
    start = comp;
    for (long long mask = 0; mask < m; mask++) {
        g.assign(n, {});
        grev.assign(n, {});
        for (long long i = 0; i < m; i++) {
            if (i == mask) {
                g[edges[i].second].push_back(edges[i].first);
                grev[edges[i].first].push_back(edges[i].second);
            } else {
                g[edges[i].first].push_back(edges[i].second);
                grev[edges[i].second].push_back(edges[i].first);
            }
        }
        used.assign(n, false);
        order.clear();
        for (long long i = 0; i < n; i++) {
            if (!used[i]) {
                topsort(i);
            }
        }
        reverse(order.begin(), order.end());
//        for (auto &i : order) {
//            cout << i << " ";
//        }
//        cout << endl;
        used.assign(n, false);
        comp.clear();
        for (auto &i : order) {
            if (!used[i]) {
                comp.push_back({});
                find_comp(i);
            }
        }
        sort(comp.begin(), comp.end());
//        for (auto &i : comp) {
//            for (auto &j : i)  {
//                cout << j << " ";
//            }
//            cout << endl;
//        }
//        cout << endl;
        if (start != comp) {
            ans++;
        }
    }
    cout << ans << " " << 1 << endl;
    THIS COUNTS ANS FOR CSS TREE*/
    if (n == m) {
        cout << n - 1 << " " << n << endl;
        return 0;
    }
    sort(not_them.begin(), not_them.end());
    not_them.resize(unique(not_them.begin(), not_them.end()) - not_them.begin());
    cout << max(1ll, min(n - 1, n - (long long) not_them.size() - 1)) << " " << 1 << endl;
    return 0;
}