CF1679D.Toss a Coin to Your Graph...

One day Masha was walking in the park and found a graph under a tree... Surprised? Did you think that this problem would have some logical and reasoned story? No way! So, the problem...

Masha has an oriented graph which $i$-th vertex contains some positive integer $a_i$. Initially Masha can put a coin at some vertex. In one operation she can move a coin placed in some vertex $u$ to any other vertex $v$ such that there is an oriented edge $u \to v$ in the graph. Each time when the coin is placed in some vertex $i$, Masha write down an integer $a_i$ in her notebook (in particular, when Masha initially puts a coin at some vertex, she writes an integer written at this vertex in her notebook). Masha wants to make exactly $k - 1$ operations in such way that the maximum number written in her notebook is as small as possible.

一天，玛莎在公园散步时在一棵树下发现了一个图……感到惊讶吗？你以为这道题会有一个逻辑清晰、合乎情理的故事背景？才不是呢！所以，题目来了……

玛莎有一个有向图，其中第 $i$ 个顶点上标有一个正整数 $a_i$。初始时，玛莎可以将一枚硬币放在某个顶点上。在一次操作中，她可以将位于顶点 $u$ 上的硬币移动到任意另一个顶点 $v$，前提是图中存在一条从 $u$ 指向 $v$ 的有向边 $u \to v$。每次硬币被放置在某个顶点 $i$ 上时，玛莎都会将该顶点上的整数 $a_i$ 记录在她的笔记本中（特别地，当玛莎最初将硬币放在某个顶点上时，她也会将该顶点上的数记入笔记本）。玛莎希望恰好进行 $k - 1$ 次操作，使得她笔记本中记录下的所有数字中的最大值尽可能小。

The first line contains three integers $n$, $m$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^5$, $1 \le k \le 10^{18}$) — the number of vertices and edges in the graph, and the number of operation that Masha should make.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$) — the numbers written in graph vertices.

Each of the following $m$ lines contains two integers $u$ and $v$ ($1 \le u \ne v \le n$) — it means that there is an edge $u \to v$ in the graph.

It's guaranteed that graph doesn't contain self-loops and multi-edges.

第一行包含三个整数 $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}$）—— 分别表示图中顶点数、边数以及玛莎需要执行的操作次数。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$）—— 表示写在图的各个顶点上的数字。

接下来的 $m$ 行中，每行包含两个整数 $u$ 和 $v$（$1 \le u \ne v \le n$）—— 表示图中存在一条从 $u$ 到 $v$ 的有向边。

保证该图不含自环和重边。

Print one integer — the minimum value of the maximum number that Masha wrote in her notebook during optimal coin movements.

If Masha won't be able to perform $k - 1$ operations, print $-1$.

输出一个整数——在最优的硬币移动方案下，玛莎在笔记本中写下的最大数字的最小值。

如果玛莎无法执行 $k - 1$ 次操作，则输出 $-1$。

Graph described in the first and the second examples is illustrated below.

In the first example Masha can initially put a coin at vertex $1$. After that she can perform three operations: $1 \to 3$, $3 \to 4$ and $4 \to 5$. Integers $1, 2, 3$ and $4$ will be written in the notepad.

In the second example Masha can initially put a coin at vertex $2$. After that she can perform $99$ operations: $2 \to 5$, $5 \to 6$, $6 \to 2$, $2 \to 5$, and so on. Integers $10, 4, 5, 10, 4, 5, \ldots, 10, 4, 5, 10$ will be written in the notepad.

In the third example Masha won't be able to perform $4$ operations.

第一个和第二个示例中所描述的图如下所示。

在第一个示例中，玛莎最初可将一枚硬币放置在顶点 $1$ 上。之后她可以执行三次操作：$1 \to 3$、$3 \to 4$ 和 $4 \to 5$。此时记事本上将依次写下整数 $1, 2, 3$ 和 $4$。

在第二个示例中，玛莎最初可将一枚硬币放置在顶点 $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$。

在第三个示例中，玛莎无法执行 $4$ 次操作。