制作精彩的电影是一件很棒的事情。如果电影的情节不可预测，那就更棒了，因为观众越是急于知道接下来会发生什么，就越能插入广告。

我们可以用一个有向图来表示所有可能的故事情节，其中顶点对应可能的场景，弧对应它们之间可能的转换。图中的一个顶点是最终场景，电影必须以该场景结束。电影中其他场景的选择由你决定，但电影必须是图中的一条有效路径，且该路径包含的场景总数不能超过 $k$ 个（因为电影长度有限）。

如果电影中存在至少两种选择下一个场景的方式，且之后仍然能在总共不超过 $k$ 个场景内到达最终场景，我们就称该场景是“不可预测的”。

电影中不可预测场景的最大可能数量是多少？注意，同一个场景可能会在电影中出现多次，在这种情况下，它的每一次出现都应单独计算。

输入格式

输入文件的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n \le 100$，$1 \le m \le 9900$，$1 \le k \le 10^{18}$），分别表示场景的数量、可能的转换数量以及电影的最大长度。最终场景是编号为 $n$ 的场景。

接下来的 $m$ 行描述了这些转换，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i \le n - 1$，$1 \le b_i \le n$，$a_i \neq b_i$），表示从场景 $a_i$ 到场景 $b_i$ 的一个可能转换。注意，不存在从最终场景出发的转换，但某些场景对之间可能存在双向转换。

输出格式

输出电影中不可预测场景的最大可能数量。

样例

输入格式 1

7 8 10
1 2
2 3
3 4
4 5
5 1
4 6
6 1
6 7

输出格式 1

2

说明

这是样例测试用例的一个场景序列：$2\ 3\ 4\ 6\ 1\ 2\ 3\ 4\ 6\ 7$。它包含 2 个不可预测场景：场景 4 的第一次出现，以及场景 6 的第一次出现。注意，这些场景的第二次出现并不是不可预测的，因为如果我们选择了不同的后续路径，就不可能在规定时间内结束电影。