你公司最新开发的游戏刚刚发布。这位穿越银河的英雄——一位四处游荡的类星体终结者——的后续冒险故事卖得不错，也收获了相当好的评价。然而，有些人抱怨游戏机制过于复杂。幸好他们不知道生产过程的真相：不眠之夜、不健康的饮食、紧张的气氛，以及一个不得不用来代替关键员工的随机数生成器……如果这一切永远不为人知，那绝对会更好。

在游戏中，玩家角色可以学习 $n$ 种技能中的一种（例如驾驶宇宙飞船、元素魔法或 PHP 编程）。技能之间通过依赖网络连接：已知有 $m$ 对 $(x, y)$，表示只有在掌握了技能 $x$ 之后才能学习技能 $y$。依赖网络中没有环，也就是说，不存在需要先掌握自身才能学习某项技能的情况。形式上，技能构成了一个有向无环图 (DAG)。

啊，我们提到过那个必须代替离职员工的随机数生成器了吗？正是它创建了技能网络。它首先随机为技能分配了编号 $1, 2, \dots, n$，然后随机抽取了 $m$ 个不同的对 $(x, y)$，满足 $x < y$，并用这些对创建了技能之间的依赖关系。这结束了程序员之间无休止的争论，大大加快了生产速度，也迫使你宣布该生成器为“月度最佳员工”。

这种技能网络的复杂程度定义为其中可以找到的最长链的长度——换句话说，就是最长的序列，使得其中的每一项技能都依赖于前一项。过高的复杂程度会导致玩家难以理解游戏机制，而且网络结构在屏幕上看起来也很糟糕。由于没有人（除了那个不愿作证的随机数生成器）理解当前的网络结构，因此做出了一个激进的决定：删除 $k$ 个技能（连同它们所有的依赖关系），使得剩余网络的复杂程度降低到尽可能小的值。

输入格式

输入的第一行包含三个整数 $n, m$ 和 $k$ ($1 \le n \le 300, 0 \le m \le 400, 0 \le k \le \min(n, 4)$)，分别表示当前技能的数量、依赖关系的个数以及要删除的技能数量。技能编号从 $1$ 到 $n$。

接下来的 $m$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x < y \le n$)，表示在学习技能 $y$ 之前必须先掌握 $x$。你可以假设这些依赖关系是按照题目描述中提到的随机方法生成的。

输出格式

输出一行一个整数——删除最多 $k$ 个技能后，技能网络可能达到的最小复杂程度。

样例

样例输入 1

6 5 1
1 3
2 3
3 4
4 5
4 6

样例输出 1

2

说明 1

如果删除技能 4，最长链的长度将为 2（例如 $1 \to 3$ 或 $2 \to 3$）。因此，最小可能的复杂程度为 2——你无法通过删除一个技能来达到长度 1。

样例输入 2

3 3 3
1 2
1 3
2 3

样例输出 2

0