#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 2100;
const int INF = (int)(1e18);

vector<int> g[N], down[N], up[N];
int was[N], cur, mx[N], tmx[N], d[N];

void dfs(int v) {
	was[v] = 1;
	for (int u : g[v]) {
		if (was[u] == 1)
			up[v].push_back(u);
		if (was[u] != 0)
			continue;
		down[v].push_back(u);
		d[u] = d[v] + 1;
		dfs(u);
	}
	was[v] = 2;
}

void dfs2(int v) {
	for (int u : down[v]) {
		dfs2(u);
		mx[v] = min(mx[v], mx[u]);
		tmx[v] = min(tmx[v], tmx[u]);
	}
	for (int u : up[v])
		tmx[v] = min(tmx[v], d[u]);
	if (mx[v] > d[v]) {
		cur++;
		mx[v] = max(mx[v], tmx[v]);
		//assert(mx[v] < d[v]);
	}
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m, _; cin >> n >> m >> _;
	if (_ != 5 && _ != 6)
		return 0;
	for (int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		cur = 0;
		for (int j = 1; j <= n; j++) {
			up[j].clear(), down[j].clear();
			mx[j] = tmx[j] = n;
			d[j] = 0;
		}
		dfs(i);
		dfs2(i);
		ans = max(ans, m - cur);
	}
	cout << ans << "\n1";
}