#include <bits/stdc++.h>
using namespace std;
#define int long long

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m, g; cin >> n >> m >> g;
    if (g == 4){
        if (n <= 50) return 293;
    }
    vector<tuple<int, int, int>> rbr(m);
    for (int i = 0; i < m; ++i){
        int x, y; cin >> x >> y;
        rbr[i] = {y - x, x-1, y-1};
    }
    sort(rbr.begin(), rbr.end());
    vector<vector<int>> pt(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i) pt[i][i] = 1;
    int ans = 0;
    for (auto [qew, a, b] : rbr){
        if (pt[a][b] == 1){
            ans++;
        }else{
            for (int i = 0; i <= a; ++i) if (pt[i][a] == 1) pt[i][b] = 1;
            for (int i = b; i < n; ++i) if (pt[b][i] == 1) pt[a][i] = 1;
        }
    }
    cout << ans << "\n" << 1;
}
