题目描述

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

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

输入格式

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

输出格式

一行一个整数表示答案。

样例

input

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

output

5

数据范围与提示

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