CF1679D Toss a Coin to Your Graph...

有一天，Masha 在公园散步时，在一棵树下发现了一个有向图……惊讶吗？你以为这道题会有一个合乎逻辑且合理的故事？没门！所以，题目如下…… Masha 有一个有向图，第 $i$ 个顶点上写着一个正整数 $a_i$。一开始，Masha 可以选择在某个顶点上放置一枚硬币。每次操作时，她可以将硬币从当前顶点 $u$ 移动到有一条有向边 $u \to v$ 的顶点 $v$。每当硬币停留在某个顶点 $i$ 时，Masha 会把该顶点上的整数 $a_i$ 记在她的笔记本上（特别地，最初放置硬币时也要记录该顶点的整数）。Masha 想要恰好进行 $k-1$ 次操作，使得她笔记本上记录的最大数字尽可能小。

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$0 \le m \le 2 \cdot 10^5$，$1 \le k \le 10^{18}$），分别表示图中的顶点数、边数和 Masha 需要进行的操作次数。 第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示每个顶点上写的数字。 接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u \ne v \le n$），表示存在一条有向边 $u \to v$。 保证图中没有自环和重边。

输出一个整数，表示在最优移动方案下，Masha 笔记本中记录的最大数字的最小可能值。 如果无法完成 $k-1$ 次操作，输出 $-1$。

下图展示了前两个样例中描述的图。  在第一个样例中，Masha 可以最初将硬币放在顶点 $1$，然后依次进行三次操作：$1 \to 3$，$3 \to 4$，$4 \to 5$。此时笔记本上会记录下整数 $1, 2, 3, 4$。 在第二个样例中，Masha 可以最初将硬币放在顶点 $2$，然后进行 $99$ 次操作：$2 \to 5$，$5 \to 6$，$6 \to 2$，$2 \to 5$，如此循环。此时笔记本上会记录下整数 $10, 4, 5, 10, 4, 5, \ldots, 10, 4, 5, 10$。 在第三个样例中，Masha 无法完成 $4$ 次操作。 由 ChatGPT 4.1 翻译