#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 2100;

int U, V;
bool was[N];
vector<int> g[N], rg[N];
vector<pair<int, int>> edge;

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);
}

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});
	}
	int ans = 0;
	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) ans++;
	}
	ans = max(ans - 1, 0ll);
	cout << ans << "\n1";
}