#6108. 「2017 山东二轮集训 Day3」第三题

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小火车的 ddl 赶不完了,他不愿意也没时间去思考题目背景到底应该怎么写了。

有一张 n 个点 m 条边的有向无环图, k 个人同时想从 1 号点走到 n 号点,每个人每个时刻都会沿着一条边走过去,不能不走(除非他们已经到达了 n 号点),不过每条边每个时刻都只能有一个人经过,请问他们中最晚的人最早什么时候能到 n 号点呢?如果不可能的话输出 -1

输入格式

第一行三个整数 n,m,k ,含义如题所述。
接下来 m 行每行两个整数 u v 表示一条边。保证不存在自环,但可能有重边。

输出格式

一行一个整数表示答案。

样例

样例输入

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

样例输出

5

数据范围与提示

对于 20\% 的数据, n \leq 20, k \leq 4
对于 50\% 的数据, n \leq 50,m,k \leq 200
对于 100\% 的数据, n \leq 100,m,k \leq 1000