有一天,玛莎在公园散步,在一棵树下发现了一张图表......惊讶吗?你认为这个问题会有一些合乎逻辑和合理的故事吗?决不!那么,问题...
Masha 有一个有向图,其中 $$$i$$$ 个顶点包含一些正整数 $$$a_i$$$。最初,玛莎可以在某个顶点放一枚硬币。在一次操作中,她可以将放置在某个顶点 $$$u$$$ 中的一枚硬币移动到任何其他顶点 $$$v$$$,以便图中存在一条定向边 $$$u \to v$$$。每次当硬币被放置在某个顶点$$$i$$$时,玛莎都会在她的笔记本中写下一个整数$$$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$$$。
示例
输入 #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
输入 #2
6 7 100 1 10 2 3 4 5 1 2 1 3 3 4 4 5 5 6 6 2 2 5
输出 #2
10
输入 #3
2 1 5 1 1 1 2
输出 #3
-1
输入#4
1 0 1 1000000000
输出#4
1000000000
注意
下面示出了第一示例和第二示例中描述的图表。
在第一个示例中,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$$$ 操作。