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

vector<vector<int>> graf;

int dfs(int v, int psk){
    if (v == psk) return 1;
    for (int u : graf[v]){
        if (dfs(u, psk) == 1) return 1;
    }
    return 0;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m, g; cin >> n >> m >> g;
    vector<tuple<int, int, int>> rbr(m);
    graf.resize(n);
    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 (dfs(a, b) == 1){
            ans++;
        }else{
            graf[a].push_back(b);
        }
    }
    cout << ans << "\n" << 1;
}
