EOJ Monthly 2019.2 (based on February Selection)

E. 中位数

单点时限: 10.0 sec

内存限制: 256 MB

“你的地图是一张白纸,所以即使想决定目的地,也不知道路在哪里。”

QQ 小方最近在自学图论。他突然想出了一个有趣的问题:

一张由 $n$ 个点,$m$ 条边构成的有向无环图。每个点有点权 $A_i$。QQ 小方想知道所有起点为 $1$ ,终点为 $n$ 的路径中最大的中位数是多少。

一条路径的中位数指的是:一条路径有 $n$ 个点,将这 $n$ 个点的权值从小到大排序后,排在位置 $\left \lfloor \frac{n}{2} \right \rfloor +1$ 上的权值。

输入格式

第 1 行输入两个正整数 $n,m$ ($1\le n\le 10^6,1\le m\le 10^6$),表示结点数量和边的数量。

第 2 行输入 $n$ 个由空格隔开的整数 $A_i$ ($0\le A_i\le 10^9$),表示点权。

接下来 $m$ 行,每行输入两个整数 $x,y$ ($1\le x,y\le n$),表示有一条 $x$ 指向 $y$ 的单向边,保证给出的图是联通的,可能存在重边。

输出格式

输出一行包含一个整数,表示最大的中位数。如果不存在任何一条起点为 $1$ ,终点为 $n$ 的路径,则输出 $-1$ 。

样例

Input
5 5
1 2 3 4 5
1 2
2 3
3 5
2 4
4 5
Output
4