#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <string>
#define endl '\n'
#define int long long

using namespace std;


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m, z;
    cin >> n >> m >> z;
    vector<pair<int, int>> seg;
    int u, v;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v;
        u--;
        v--;
        if ((u + 1) % n != v) {
            seg.push_back({u, v});
        }
    }
    int calc = 0;
    while (!seg.empty()) {
        vector<pair<int, int>> ev;
        for (int i = 0; i < (int)seg.size(); ++i) {
            if (seg[i].first > seg[i].second) {
                ev.push_back({seg[i].first, -1});
                ev.push_back({n - 1, 1});
                ev.push_back({0, -1});
                ev.push_back({seg[i].second, 1});
            } else {
                ev.push_back({seg[i].first, -1});
                ev.push_back({seg[i].second, 1});
            }
        }
        int ind = 0;
        sort(ev.begin(), ev.end());
        int cur = 0;
        int ii = 0;
        int bal = 0;
        for (int i = 0; i < n; ++i) {
            while (ind < (int)ev.size() && ev[ind].first == i && ev[ind].second == -1) {
                bal++;
                ind++;
            }
            if (bal > cur) {
                cur = bal;
                ii = i;
            }
            while (ind < (int)ev.size() && ev[ind].first == i && ev[ind].second == 1) {
                bal--;
                ind++;
            }
        }
        calc++;
        vector<pair<int, int>> nw;
        for (int i = 0; i < (int)seg.size(); ++i) {
            if (seg[i].first < seg[i].second && seg[i].first <= ii && ii <= seg[i].second) {
                continue;
            } else if (seg[i].first > seg[i].second && (seg[i].first <= ii || ii <= seg[i].second)) {
                continue;
            } else {
                nw.push_back(seg[i]);
            }
        }
        seg = nw;
    }
    cout << (n - calc) << endl;
    cout << 1 << endl;
    return 0;
}
