[AdditionalFile5228.zip](file://AdditionalFile5228.zip?type=additional_file)

#5228. 「UOI 2021 Stage 4 Day1」数字图

标签: 传统 | 时间限制: 4000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2021 Stage 4 Day1 T3. Числовий граф

瓦西里和彼得里克发现了一个数字图——这是一个连通的有向图，每一个顶点上都写有一个数字。

他们早就想要得到一个数字，于是决定在这个图上玩一个游戏。他们将棋子放在编号为 $1$ 的顶点上。每一回合，玩家可以选择：

• 结束游戏并取走当前棋子所在顶点上的数字；
• 或者将棋子沿着有向边移动到相邻的顶点。

如果游戏进行了 $10^{100}$ 步后仍未结束，游戏将自动终止，玩家将取走当时棋子所在顶点的数字。

瓦西里先开始游戏，他希望最大化最终得到的数字，而彼得里克则希望最小化这个数字。假设双方都采用最优策略，求最终他们将得到的数字。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n \leq 250000, 1 \leq m \leq 500000)$，分别表示图的顶点数和边数。

第二行包含 $n$ 个整数 $a_i$ $(1 \leq a_i \leq 10^{9})$，表示图上每个顶点上的数字。

接下来的 $m$ 行，每行包含两个整数 $x$ 和 $y$ $(1 \leq x, y \leq n)$，表示存在一条从 $x$ 到 $y$ 的有向边。

输出格式

输出一行，包含一个整数，表示在双方都采用最优策略的情况下，最终得到的数字。

样例 1

输入

4 4
1 10 4 5
1 2
2 3
2 4
3 1

输出

4

在第一个样例中，图如图 1 所示。顶点上标注了顶点编号和游戏中的数字（括号内）。

1. 瓦西里首先行动，他可以选择立即结束游戏，或者移动到顶点 $2$。移动到顶点 $2$ 是更好的选择。
2. 接着彼得里克行动，他会选择移动到顶点 $3$，因为这样对他有利。
3. 最后，如果瓦西里移动到顶点 $1$，彼得里克会结束游戏并得到数字 $1$，因此瓦西里更倾向于立即结束游戏，得到数字 $4$。

样例 2

输入

2 2
1 2
1 2
2 1

输出

1

在第二个样例中，图如图 2 所示。双方会轮流移动整整 $10^{100}$ 步，最终棋子停在顶点 $1$。

数据范围与提示

详细子任务附加限制及分值如下表所示：