题目描述

Gabiluso 是他所在国家最出色的间谍之一。现在，他正在执行一项“不可能完成”的任务——延缓 Colugu 市的军队抵达机场的速度。Colugu 市有 $n$ 个公交车站和 $m$ 条道路。每条道路直接连接两个公交车站，且所有道路都是单向的。为了保持空气清洁，政府禁止所有军用车辆通行。因此，军队必须乘坐公交车前往机场。两个公交车站之间可能存在多条道路。如果一个公交车站被摧毁，所有连接该车站的道路都将无法使用。Gabiluso 需要做的是摧毁一些公交车站，使得军队无法在 $k$ 分钟内到达机场。公交车通过任何一条道路都需要恰好 $1$ 分钟。所有公交车站的编号从 $1$ 到 $n$。编号为 $1$ 的公交车站位于军营，编号为 $n$ 的车站位于机场。军队总是从 $1$ 号车站出发。

由于重兵把守，$1$ 号车站和 $n$ 号车站不能被摧毁。当然，也没有从 $1$ 号车站直接到 $n$ 号车站的道路。

请帮助 Gabiluso 计算他必须摧毁的最少公交车站数量，以完成任务。

输入：

输入包含多个测试用例。输入以三个 $0$ 结束。

对于每个测试用例：

第一行包含 $3$ 个整数：$n$、$m$ 和 $k$。$(0 < n \le 50, 0 < m \le 4000, 0 < k < 1000)$

接下来是 $m$ 行，每行包含 $2$ 个整数 $s$ 和 $f$，表示存在一条从 $s$ 号车站到 $f$ 号车站的道路。

输出：

对于每个测试用例，输出 Gabiluso 必须摧毁的最少车站数量。

示例输入：

5 7 3 
1 3 
3 4 
4 5 
1 2 
2 5 
1 4 
4 5 
0 0 0

示例输出：

2