← 返回题目列表

Codeforces · 1679/D

D. 向你的图表扔一枚硬币......

中文机器翻译题面 查看原题

有一天,玛莎在公园散步,在一棵树下发现了一张图表......惊讶吗?你认为这个问题会有一些合乎逻辑和合理的故事吗?决不!那么,问题...

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$$$ 操作。