问题 26030 --摧毁巴士站

26030: 摧毁巴士站

时间限制: 1 Sec  内存限制: 128 MB
提交: 41  解决: 21
[提交][状态][讨论版][命题人:]

题目描述

Gabiluso是最伟大的间谍之一。现在,他试图完成一个“不可能完成”的使命――减缓Colugu的军队到达机场的时间。Colugun个公共汽车站和m条道路。每条道路直接连接两个巴士站,所有的道路都是单向的。为了保持空气洁净,政府禁止所有军用车辆,因此,军队必须乘搭巴士去机场。两个巴士站之间,可能有超过一条道路。如果一个公共汽车站被破坏时,所有连接该站的道路将无法运作。Gabiluso需要做的是摧毁了一些公共汽车站,使军队无法在K分钟内到达机场。一辆公交车通过一条道路,都是一分钟。所有巴士站的编号从1n1号巴士站是在军营,第n号站是机场。军队始终从第一站出发。第一站和第n站不能被破坏,这里有大量的防御力量。当然也没有从第一站到第n站的道路。

请帮助Gabiluso来计算能完成使命所需摧毁的最低数目的巴士站。

输入

第一行包含三个整数nmk (2<n<=50,0<m<=4000,0<k<1000)

接下来m行,每行2个整数sf,表示从站s到站f有一条路。

输出

输出最少需要摧毁的巴士站数目。

样例输入

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

样例输出

2

提示


【数据规模】


30%的数据N<=15

来源

 

[提交][状态]