#pragma GCC optimize('Ofast')
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
struct fenw {
    vector<int> f;
    explicit fenw(int n) {
        f.resize(n);
    }
    void upd(int i, int x) {
        while (i < f.size()) {
            f[i] += x;
            i |= (i + 1);
        }
    }
    int get(int i) {
        int sum = 0;
        while (i >= 0) {
            sum += f[i];
            i %= (i + 1);
            i--;
        }
        return sum;
    }
};
template <typename T>
bool smin(T& a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
bool smax(T& a, T b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}
vector<vector<pair<int, int>>> g;
vector<int> used;
int ban = -1;
int cnt = 0;
void dfs(int v) {
    used[v] = 1;
    for (auto [e, i] : g[v]) {
        if (used[e] == 0 && i != ban) {
            dfs(e);
        }
    }
    used[v] = 2;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, _;
    cin >> n >> m >> _;
    if (n == m) {
        cout << n - 1 << ' ' << n << '\n';
        return 0;
    }
    g.resize(n);
    used.assign(m, 0);
    vector<vector<pair<int, int>>> r(2 * n);
    vector<tuple<int, int, int>> all;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v, u--, v--;
        if ((u + 1) % n == v) {
            used[i] = 1;
            continue;
        }
        swap(u, v);
        r[v].emplace_back(1, i);
        r[(u < v ? u + n : u)].emplace_back(-1, i);
        all.emplace_back(v, u, i);
    }

    for (int i = 0; i < 2 * n; i++) sort(r[i].begin(), r[i].end());
    for (int i = 0; i < n; i++) {
        cnt++;
        int maxc = 0, indc = -1;
        int no = 0;
        vector<int> tof(n);
        for (int j = 0; j < 2 * n; j++) {
            for (auto [ty, ind] : r[j]) {
                if (!used[ind]) {
                    no += ty;
                }
            }
            if (j < n) {
                tof[j] = no;
            } else {
                if (smax(maxc, no + tof[j - n])) {
                    indc = j;
                }
            }
        }
        indc -= n;
        for (auto [v, u, j] : all) {
            if (v < u) {
                if (v <= indc && u > indc) used[j] = 1;
            } else {
                if (indc < u || indc >= v) used[j] = 1;
            }
        }
        bool flag = true;
        for (auto e : used) {
            if (!e) flag = false;
        }
        if (flag) break;
    }
    cout << cnt << ' ' << 1 << '\n';
    return 0;
}