
// #pragma GCC optmize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()

typedef long long ll;
typedef long double ld;

template <typename T>
void sort(T &s) {
    sort(all(s));
}

template<typename T>
void rsort(T &s) {
    sort(rall(s));
}

const int inf = 2e9 + 2000;
const ll infll = 2e18 + 2000;
const int R = (1 << 20);
mt19937 rnd(26);

template <typename T>
struct point {
    T x, y;
    point(T x, T y) : x(x), y(y) {}
    point(point a, point b) : x(b.x - a.x), y(b.y - a.y) {}

    point operator + (point &o) const {
        return {x + o.x, y + o.y};
    }

    point operator * (const T k) const {
        return {x * k, y * k};
    }

    T operator * (const point &o) const {
        return x * o.x + y * o.y;
    }

    T operator % (const point &o) const {
        return x * o.y - y * o.x;
    }

    T len2() {
        return x * x + y * y;
    }

    ld len() {
        return sqrt(x * x + y * y);
    }
};

vector<vector<pair<int, int> > > g, gobr;


void solve() {
    int n, m, gr;
    cin >> n >> m >> gr;

    if (gr == 3 || gr == 4) {
        cout << m - n + 1 << ' ' << 1;
    } else if (gr == 5 || gr == 6) {
        g.resize(n);
        gobr.resize(n);

        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;

            g[a - 1].emplace_back(b - 1, i);
            gobr[b - 1].emplace_back(a - 1, i);
        }

        set<int> se;
        set<int> ko2;

        for (int i = 0; i < n; ++i) {
            if (g[i].size() == 1 && gobr[i].size() == 1) {
                ko2.insert(i);
            } else if (g[i].size() == 1) {
                se.insert(g[i][0].second);
            } else if (gobr[i].size() == 1) {
                se.insert(gobr[i][0].second);
            }
        }

        while (!ko2.empty()) {
            vector<int> del;
            for (auto i : ko2) {
                if (se.find(g[i][0].second) != se.end()) {
                    if (se.find(gobr[i][0].second) != se.end()) {
                        del.push_back(i);
                    } else {
                        se.insert(gobr[i][0].second);
                        del.push_back(i);
                    }
                } else {
                    if (se.find(gobr[i][0].second) != se.end()) {
                        se.insert(g[i][0].second);
                        del.push_back(i);
                    }
                }
            }

            if (del.empty()) {
                se.insert(g[*ko2.begin()][0].second);
                se.erase(ko2.begin());
            } else {
                for (auto i : del) {
                    se.erase(i);
                }
            }
        }

        if (se.size() == m) {
            cout << m - 1 << ' ' << m;
        } else {
            cout << se.size() << ' ' << 1;
        }
    }
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int tt = 1;
    // cin >> tt;

    while (tt--) {
        solve();
    }
}
