#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;

void fast_in_out() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

#define int long long
#define all(x) (x).begin(), (x).end()
using ll = long long;
using ull = long long;
using ld = long double;
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 2e3;
vector<int> g[N];
pair<int, int> ed[N];
int n, m, G;
int d[N][N];
int p[N], sz[N];

void dfs(int v, int lead) {
    d[lead][v] = 1;
    for (auto to: g[v]) {
        if (d[lead][v] == 0) {
            dfs(to, lead);
        }
    }
}

int par(int v) {
    return p[v] = (p[v] == v ? v : par(p[v]));
}

void unite(int x, int y) {
    x = par(x);
    y = par(y);
    if (x != y) {
        if (sz[x] < sz[y]) {
            swap(x, y);
        }
        sz[x] += sz[y];
        p[y] = x;
    }
}

int komp() {
    for (int i = 0; i < n; ++i) {
        dfs(i, i);
    }
    for (int i = 0; i < n; ++i) {
        sz[i] = 1;
        p[i] = i;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (d[i][j] && d[j][i]) {
                unite(i, j);
            }
        }
    }
    set<int> st;
    for (int i = 0; i < n; ++i) {
        st.insert(par(i));
    }
    return ((int) st.size());
}

void solve() {
    cin >> n >> m >> G;
    for (int i = 0; i < m; ++i) {
        cin >> ed[i].first >> ed[i].second;
        --ed[i].first;
        --ed[i].second;
        if ((ed[i].second - ed[i].first + n) % n != 1) {
            g[ed[i].first].emplace_back(ed[i].second);
        }
    }
    cout << n - komp() + 1 << '\n' << 0;
}

signed main() {
    fast_in_out();
    int qwe = 1;
//    cin >> qwe;
    while (qwe--) {
        solve();
    }
    return 0;
}
