#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 2100;

int U, V, cc[N];
bool was[N];
vector<int> g[N], rg[N], ng[N], nrg[N], gg[N];
vector<pair<int, int>> edge, sedge;

void dfs1(int v) {
	was[v] = true;
	for (int u : g[v])
		if (!was[u] && (v != U || u != V))
			dfs1(u);
}

void dfs2(int v) {
	was[v] = true;
	for (int u : rg[v])
		if (!was[u] && (v != V || u != U))
			dfs2(u);
}


int cnt = 0;

vector<int> topo;
void dfs3(int v) {
	was[v] = true;
	for (int u : ng[v])
		if (!was[u])
			dfs3(u);
	topo.push_back(v);
}

void dfs4(int v) {
	cc[v] = cnt;
	was[v] = true;
	for (int u : nrg[v])
		if (!was[u])
			dfs4(u);
}

void dfs5(int v) {
	was[v] = true;
	for (int u : gg[v])
		if (!was[u])
			dfs5(u);
}

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);
		rg[v].push_back(u);
		edge.push_back({u, v});
	}
	for (auto [u, v] : edge) {
		U = u;
		V = v;
		bool can = false;
		dfs1(1);
		for (int j = 1; j <= n; j++) {
			if (!was[j])
				can = true;
			was[j] = false;
		}
		dfs2(1);
		for (int j = 1; j <= n; j++) {
			if (!was[j])
				can = true;
			was[j] = false;
		}
		if (!can) {
			ng[u].push_back(v);
			nrg[v].push_back(u);
		} else sedge.push_back({u, v});
	}
	for (int i = 1; i <= n; i++)
		if (!was[i]) dfs3(i);
	reverse(begin(topo), end(topo));
	for (int i = 1; i <= n; i++)
		was[i] = false;
	for (int i = 1; i <= n; i++)
		if (!was[i]) {
			cnt++;
			dfs4(i);
		}
	for (auto [u, v] : sedge) {
		gg[cc[u]].push_back(cc[v]);
		gg[cc[v]].push_back(cc[u]);
	}
	for (int i = 1; i <= cnt; i++)
		was[i] = false;
	int ans = cnt;
	for (int i = 1; i <= cnt; i++)
		if (!was[i]) {
			ans--;
			dfs5(i);
		}
	cout << ans << "\n1";
}