{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\n\u003cdiv class\u003d\"panel_content\"\u003e\n Gabiluso是他国最伟大的间谍之一。现在,他正在尝试完成一个“不可能的”任务——让City Colugu的军队到达机场变得缓慢。City Colugu有n个公交车站和m条道路。每条道路直接连接两个公交车站,而且所有道路都是单行道。为了保持空气清洁,政府禁止所有军用车辆。因此,军队必须乘坐公交车前往机场。两个公交车站之间可能有多条道路。如果一个公交车站被摧毁,与该车站相连的所有道路都将无法使用。Gabiluso需要做的是摧毁一些公交车站,以使军队在k分钟内无法到达机场。公交车通过任何道路需要正好一分钟的时间。所有公交车站编号从1到n。第1号车站位于军营,第n号车站位于机场。军队总是从第1号车站出发。\n \u003cbr\u003e\n 第1号车站和第n号车站因为有重兵把守,所以不能被摧毁。当然,从第1号车站到第n号车站也没有道路。\n \u003cbr\u003e\n \u003cbr\u003e\n \u003cbr\u003e\n 请帮助Gabiluso计算他必须摧毁的最小公交车站数量,以完成他的任务。\n \u003cbr\u003e\n\u003c/div\u003e\n"}},{"title":"Input","value":{"format":"HTML","content":"有几个测试案例。输入以三个零结束。\n\u003cbr\u003e\n\u003cbr\u003e\n对于每个测试案例:\n\u003cbr\u003e\n\u003cbr\u003e\n第一行包含3个整数,n、m和k。(0 \u003c n \u003c\u003d 50,0 \u003c m \u003c\u003d 4000,0 \u003c k \u003c 1000)\n\u003cbr\u003e\n然后是m行。每行包含2个整数,s和f,表示从车站s到车站f有一条道路。\n\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"对于每个测试案例,输出Gabiluso必须摧毁的最小车站数量。"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 7 3\r\n1 3\r\n3 4\r\n4 5\r\n1 2\r\n2 5\r\n1 4\r\n4 5\r\n0 0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}