#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 2100;

int n, m, _, oo[N], cc[N];
bool was[N];
vector<int> g[N], rg[N];
vector<pair<int, int>> edge;

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

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

void comps(vector<pair<int, int>> edge) {
	for (int i = 1; i <= n; i++)
		g[i].clear(), rg[i].clear();
	for (auto [u, v] : edge)
		g[u].push_back(v), rg[v].push_back(u);
	topo.clear();
	cnt = 0;
	for (int i = 1; i <= n; i++)
		was[i] = false;
	for (int i = 1; i <= n; i++)
		if (!was[i]) dfs1(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++;
			dfs2(i);
		}
	int pos = 1;
	for (int i = 1; i <= n; i++) {
		int cur = cc[i];
		cc[i] = pos;
		if (i < n && cur != cc[i + 1])
			pos++;
	}
}

bool used[N];

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> _;
	if (_ != 5 && _ != 6)
		return 0;
	for (int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		edge.push_back({u, v});
	}
	for (int i = 1; i <= n; i++)
		oo[i] = 1;
	int ans = 0;
	for (int i = 0; i < m; i++) {
		if (oo[edge[i].first] != oo[edge[i].second]) {
			used[i] = true;
			ans++;
			continue;
		}
		vector<pair<int, int>> sedge;
		for (int j = 0; j < m; j++)
			if (i != j && !used[j])
				sedge.push_back(edge[j]);
		comps(sedge);
		bool good = false;
		for (int j = 1; j <= n; j++)
			if (cc[j] != oo[j]) {
				oo[j] = cc[j];
				good = true;
			}
		if (good) ans++, used[i] = true;
	}
	cout << ans << "\n1";
}