#include <bits/stdc++.h>

constexpr int MAXN = 300;

int n, k;

struct Edge {
	int next;
	int depth;
	Edge() {}
	Edge(int next, int depth = 0) : next(next), depth(depth) {}
};

struct Node {
	std::vector<Edge> edge;
	std::vector<int> prev;
	int depth;
};

typedef Node Graph[MAXN];
Graph graph;

struct Backtrack {
	int r;

	bool blocked[MAXN];
	struct Level {
		int prev_depth[MAXN];
		int modified[MAXN];
		int count;
		Level()
		{
			for (int i = 0; i < n; i++)
				prev_depth[i] = -1;
			count = 0;
		}
		void Add(int v) { modified[count++] = v; }
		void Set(int v, int new_depth);
		void TrySet(int v);
		void Undo();

		void PrintDepths()
		{
			for (int i = 0; i < n; i++)
				std::cout << i << ":" << graph[i].depth << "(" << prev_depth[i] << ") ";
			std::cout << std::endl;
		}
	};
	Level level[4];

	Backtrack()
	{
		for (int i = 0; i < n; i++)
			blocked[i] = false;
	}

	int MaxDepthNode()
	{
		int v = -1;
		int res = 0;
		for (int i = 0; i < n; i++)
			if (graph[i].depth > res) {
				res = graph[i].depth;
				v = i;
			}
		return v;
	}

	bool BT(int k, int v);
	bool BT(int k);

	bool IsGood(int r)
	{
		//std::cout << r << "\n";
		this->r = r;
		return BT(k);
	}
};

void Backtrack::Level::Undo()
{
	for (int i = 0; i < count; i++) {
		int v = modified[i];
		graph[v].depth = prev_depth[v];
		prev_depth[v] = -1;
	}
	count = 0;
}

void Backtrack::Level::TrySet(int v)
{
	if (prev_depth[v] >= 0)
		return;
	Node& node = graph[v];
	if (node.depth == 0)
		return;
	int depth = 1;
	for (auto e : node.edge)
		depth = std::max(depth, graph[e.next].depth + 1);
	if (depth < node.depth)
		Set(v, depth);
}

void Backtrack::Level::Set(int v, int new_depth)
{
	prev_depth[v] = graph[v].depth;
	graph[v].depth = new_depth;
	Add(v);
	for (auto w : graph[v].prev)
		TrySet(w);
}

bool Backtrack::BT(int k, int v)
{
	//std::cout << "BT(" << k << "," << v << ") - Set\n";
	level[k].Set(v, 0);
	//level[k].PrintDepths();
	bool res = BT(k);
	level[k].Undo();
	//std::cout << "BT(" << k << "," << v << ") - Undo\n";
	//level[k].PrintDepths();
	return res;
}

bool Backtrack::BT(int k)
{
	int v = MaxDepthNode();
	if (v < 0)
		return true;
	int depth = graph[v].depth;
	if (depth <= r)
		return true;
	if (depth / (k + 1) > r)
		return false;
	// (depth - min_single - 1) / k < r + 1
	// depth - 1 - k(r + 1) < min_single
	int min_single = depth - k * (r + 1);
	for (int d = 0; d < depth; d++) {
		if (d >= min_single && d + min_single < depth) {
			if (BT(k - 1, v))
				return true;
		}
		if (d < depth - 1) {
			int next_depth = depth - d - 1;
			for (auto e : graph[v].edge) {
				int w = e.next;
				if (graph[w].depth == next_depth) {
					v = w;
					break;
				}
			}
		}
	}
	return false;
}

void BuildDephts()
{
	for (int i = n - 1; i >= 0; i--) {
		Node& node = graph[i];
		node.depth = 1;
		for (auto e : node.edge)
			node.depth = std::max(node.depth, graph[e.next].depth + 1);
	}
}

void BuildPrev()
{
	for (int i = 0; i < n; i++)
		for (auto e : graph[i].edge)
			graph[e.next].prev.push_back(i);
}

struct TopolSort {
	std::vector<bool> visited;
	std::vector<int> order;

	void DFS(int v)
	{
		if (visited[v])
			return;
		visited[v] = true;
		for (auto e : graph[v].edge)
			DFS(e.next);
		order.push_back(v);
	}

	TopolSort()
	{
		visited.resize(n, false);
		for (int i = 0; i < n; i++)
			DFS(i);
		std::reverse(order.begin(), order.end());
		int inv[n];
		for (int i = 0; i < n; i++)
			inv[order[i]] = i;

		Graph sorted;
		for (int i = 0; i < n; i++) {
			int v = order[i];
			for (auto e : graph[v].edge)
				sorted[i].edge.push_back(Edge(inv[e.next]));
		}
		for (int i = 0; i < n; i++)
			graph[i] = std::move(sorted[i]);
	}
};

void read(int m)
{
	while (m--) {
		int a, b;
		std::cin >> a >> b;
		graph[--a].edge.push_back(Edge(--b));
	}
}

void gen(int m);
void PrintGraph();

int main()
{
	int m;
	std::ios_base::sync_with_stdio(false);
	std::cin >> n >> m >> k;
	//n = 40; m = 400; k = 4;
	read(m);
	//gen(m);
	TopolSort();
	//PrintGraph();
	BuildPrev();
	BuildDephts();
	Backtrack bt;
	int max_depth = graph[bt.MaxDepthNode()].depth;
	int l = 0, p = 1;
	if (max_depth == 0 || bt.IsGood(0))
		p = 0;
	else {
		while (p <= max_depth)
			if (!bt.IsGood(p)) {
				l = p;
				p = std::min(2 * p, max_depth);
			}
			else
				break;
		while (l + 1 < p) {
			int m = (l + p) / 2;
			if (bt.IsGood(m))
				p = m;
			else
				l = m;
		}
	}
	std::cout << p << std::endl;
	return 0;
}

void gen(int m)
{
	std::vector<std::pair<int, int>> edges;
	int p[n];
	for (int i = 0; i < n; i++)
		p[i] = i;
	std::random_shuffle(p, p + n);
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			edges.push_back(std::make_pair(i, j));
	std::random_shuffle(edges.begin(), edges.end());
	for (auto e : edges) {
		int a = p[e.first];
		int b = p[e.second];
		graph[a].edge.push_back(b);
		if (--m == 0)
			break;
	}
}

void PrintGraph()
{
	for (int i = 0; i < n; i++) {
		std::cout << i << ":";
		for (auto e : graph[i].edge)
			std::cout << ' ' << e.next;
		std::cout << std::endl;
	}
}