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

传统 1000 ms 512 MiB

$36$ 通过 $66$ 提交

题目描述

小火车的 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$。