A6030. 「2017 山东二轮集训 Day3」第三题
编程题
提高+/省选-
知识点
题目描述
小火车的 ddl 赶不完了，他不愿意也没时间去思考题目背景到底应该怎么写了。
有一张 $ n $ 个点 $ m $ 条边的有向无环图，$ k $ 个人同时想从 $ 1 $ 号点走到 $ n $ 号点，每个人每个时刻都会沿着一条边走过去，不能不走（除非他们已经到达了 $ n $ 号点），不过每条边每个时刻都只能有一个人经过，请问他们中最晚的人最早什么时候能到 $ n $ 号点呢？如果不可能的话输出 $ -1 $。
有一张 $ n $ 个点 $ m $ 条边的有向无环图，$ k $ 个人同时想从 $ 1 $ 号点走到 $ n $ 号点，每个人每个时刻都会沿着一条边走过去，不能不走（除非他们已经到达了 $ n $ 号点），不过每条边每个时刻都只能有一个人经过，请问他们中最晚的人最早什么时候能到 $ n $ 号点呢？如果不可能的话输出 $ -1 $。
输入格式
第一行三个整数 $ n,m,k $，含义如题所述。
接下来 $ m $ 行每行两个整数 $ u $ 和 $ v $ 表示一条边。保证不存在自环，但可能有重边。
接下来 $ m $ 行每行两个整数 $ u $ 和 $ v $ 表示一条边。保证不存在自环，但可能有重边。
输出格式
一行一个整数表示答案。
输入输出样例
输入 #1
8 11 3 1 2 1 3 1 4 6 7 2 5 3 6 3 2 4 6 5 7 7 8 2 7
输出 #1
5
说明/提示
对于 $ 20\% $ 的数据，$ n \leq 20, k \leq 4 $；
对于 $ 50\% $ 的数据，$ n \leq 50,m,k \leq 200 $；
对于 $ 100\% $ 的数据，$ n \leq 100,m,k \leq 1000 $。
对于 $ 50\% $ 的数据，$ n \leq 50,m,k \leq 200 $；
对于 $ 100\% $ 的数据，$ n \leq 100,m,k \leq 1000 $。