//#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;
vector<long long> tin, tout;
long long timee = 0, ans = 0;

void dfs(long long v) {
    tin[v] = timee;
    timee++;
    for (auto &i : g[v]) {
        if (tin[i] == -1) {
            dfs(i);
        } else {
            if (tin[v] <= tin[i] && tout[i] <= tout[v]) {
                ans++;
            }
        }
    }
    tout[v] = timee;
    timee++;
}


signed main() {
    //ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    long long n, m, t;
    cin >> n >> m >> t;
    if (t == 3) {
        cout << m - n + 1 << " " << 1 << endl;
    }
    g.resize(n);
    for (long long i = 0; i < m; i++) {
        long long u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
    }
    tin.resize(n, -1);
    tout.resize(n);
    for (long long i = 0; i < n; i++) {
        if (tin[i] == -1) {
            dfs(i);
        }
    }
    cout << ans << " " << 1 << endl;
    return 0;
    if (m == n) {
        cout << n - 1 << " " << 1 << endl;
        return 0;
    }
    cout << max(0ll, n - (m - n) - 1) << " " << 1 << endl;
}