// i must be the reason why
// you have given up your smiles
// and the hope inside your life has been stolen
// i must be the reason why
// you have told me all these lies
// that i will lead a happier life without you by my side
// дальше текст забыл

// t.me/truebaza <---- лучший тг канал
// t.me/truebaza <---- лучший тг канал
// t.me/truebaza <---- лучший тг канал
// t.me/truebaza <---- лучший тг канал
// t.me/truebaza <---- лучший тг канал
// t.me/truebaza <---- лучший тг канал
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define int long long
#define fastio cin.tie(0), ios_base::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define INF ((1ll << 60) - 1)

vector<vector<int>> g;
vector<bool> visited;

bool reach(int v, int w) {
    if (v == w) {
        return true;
    }
    visited[v] = true;
    for (auto we : g[v]) {
        if (!visited[we] && reach(we, w)) {
            return true;
        }
    }
    return false;
}

auto main() -> signed { // t.me/truebaza <---- лучший тг канал,
    fastio;
    int n, m, KEK;
    cin >> n >> m >> KEK;
    vector<vector<int>> oldg(n);
    g.resize(n);
    oldg.resize(n);
    for (int i = 0; i < m; ++i) {
        int v, w;
        cin >> v >> w;
        v--, w--;
        oldg[v].push_back(w);
    }
    int res = m;
    visited.resize(n);
    for (int i = n - 1; i >= 0; --i) {
        sort(all(oldg[i]));
        for (auto w : oldg[i]) {
            fill(all(visited), false);
            if (!reach(i, w)) {
                g[i].push_back(w);
                res--;
            }
        }
    }
    cout << res << '\n' << 1 << '\n';
}