图上投币

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一个有向图，顶点 $i$ 的权值为正整数 $a_i$。你可任选起点放置硬币，随后沿有向边移动恰好 $k-1$ 次。求经过的 $k$ 个顶点中最大权值的最小可能值；若不存在长度为 $k$ 个顶点的有向游走，输出 $-1$。

输入格式

第一行三个整数 $n,m,k$。第二行包含 $n$ 个顶点权值。接下来 $m$ 行每行两个整数 $u,v$，表示有向边 $u\to v$。

输出格式

输出最小可能的最大顶点权值；无法完成则输出 $-1$。

样例输入 1

6 7 4
1 10 2 3 4 5
1 2
1 3
3 4
4 5
5 6
6 2
2 5

样例输出 1

4

数据范围

• $1\le n\le2\times10^5$，$0\le m\le2\times10^5$；
• $1\le k\le10^{18}$；
• $1\le a_i\le10^9$；
• 图中无自环和重边。

本题采用独立测试点计分，每个测试点等分。

提示

固定允许的最大权值后，只保留权值不超过它的顶点。若子图有环，就能得到任意长游走；否则只需计算 DAG 最长路。