#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#define int long long

using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, g;
    cin >> n >> m >> g;
    vector<pair<int, int>> q;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        if (abs(u - v) > 1) {
            q.push_back({min(u, v), -(i + 1)});
            q.push_back({max(u, v), i + 1});
        }
    }
    set<int> ans;
    sort(q.begin(), q.end());
    int b = 0;
    set<int> open;
    for (int i = 0; i < q.size(); ++i) {
        if (q[i].second <= -1) {
            open.insert(-q[i].second - 1);
            b++;
        } else {
            open.erase(q[i].second - 1);
            b--;
        }
        while (i < q.size() && q[i].first == q[i + 1].first) {
            i++;
            if (q[i].first <= -1) {
                open.insert(-q[i].second - 1);
                b++;
            } else {
                open.erase(q[i].second - 1);
                b--;
            }
        }
        if (b == 1) {
            ans.insert(*open.begin());
        }
    }
    cout << ans.size() << ' ' << 1;
}
