#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
        tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,
        tree_order_statistics_node_update>;

#define int long long

vector<vector<int>> g;
vector<int> used;

void dfs(int v) {
    used[v] = 1;
    for (auto to: g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
}

signed main() {
    int n, m, g1;
    cin >> n >> m >> g1;
    vector<pair<int, int>> ed;
    g.resize(n);
    used.resize(n, 0);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        if ((v - u + n) % n == 1) {
            continue;
        }
        ed.emplace_back(u - 1, v - 1);
        g[u - 1].push_back(v - 1);
    }
    vector<pair<int, int>> otr;
    vector<int> nxt(n);
    vector<vector<int>> pr(2 * n);
    int mn = n - 1;
    for (int i = 0; i < n; ++i) {
        used.assign(n, 0);
        dfs(i);
        int ind = -1;
        for (int j = i + 1; j <= i + n; ++j) {
            if (used[j % n]) {
                ind = j;
                break;
            }
        }
        otr.push_back({i, ind - 1});
        nxt[i] = ind - 1;
        mn = min(mn, ind - 1);
        pr[ind].push_back(i);
    }
    int ans = 10000;
    for (int i = 0; i <= mn; ++i) {
        vector<pair<int, int>> ot;
        int curr = 1;
        for (int j = i + 1; j < i + n; ++j) {
            if (nxt[j] < i + n) {
                ot.push_back({nxt[j] - i, j - i});
            }
        }
        sort(ot.begin(), ot.end());
        int last = 0;
        for (auto to: ot) {
            if (to.second > last) {
                last = to.first;
                curr++;
            }
        }
        ans = min(ans, curr);
    }
    cout << n - ans << "\n" << 1;
    return 0;
}
