#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <array>
#include <queue>

using namespace std;
typedef long long ll;
typedef long double ld;
#define all(a) a.begin(), a.end()
const ll N = 2001;
ll n, m, group;
void calcDAGdfs(ll u, ll nch, vector<vector<ll>>& g, vector<vector<char>>& p, vector<ll>& us) {
	p[nch][u] = 1;
	us[u] = nch;
	for (ll v : g[u]) {
		if (us[v] < nch) {
			calcDAGdfs(v, nch, g, p, us);
		}
	}
}
ll calcDAG(vector<vector<ll>>& g) {
	ll n = g.size();
	vector<vector<char>> p(n, vector<char>(n, 0));
	vector<ll> us(n, -1);
	for (ll u = 0; u < n; u++) {
		calcDAGdfs(u, u, g, p, us);
		p[u][u] = 0;
	}
	ll res = 0;
	for (ll u = 0; u < n; u++) {
		for (ll v : g[u]) {
			char is = 1;
			for (ll k = 0; k < n; k++) {
				is &= !(p[u][k] && p[k][v]);
			}
			res += is;
		}
	}
	return res;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> group;
	vector<vector<ll>> g(n + 1);
	for (ll i = 0; i < m; i++) {
		ll u, v;
		cin >> u >> v;
		g[u].push_back(v);
	}
	cout << m - calcDAG(g) << "\n1\n";
	return 0;
}